Калькулятор функції Ейлера (тотента)

Про цей калькулятор

Функція Ейлера (тотієнт) φ(n) підраховує, скільки цілих чисел від 1 до n не мають спільного дільника з n, і її обчислюють за розкладом n на прості множники як φ(n) = n × ∏(1 − 1/p) за кожним різним простим p, що ділить n. Для самого простого числа p маємо φ(p) = p − 1, бо кожне менше додатне ціле число автоматично взаємно просте з ним.

Функція Ейлера є математичним рушієм шифрування RSA: під час генерації ключів множать два великі прості числа p і q, щоб отримати n = pq, а потім використовують φ(n) = (p−1)(q−1) для обчислення дійсної пари відкритого та закритого показників. Вона також лежить в основі теореми Ейлера в теорії чисел, яку застосовують для знаходження обернених за модулем і зменшення великих показників у криптографічних обчисленнях та обчисленнях зі спортивного програмування.