Функция Эйлера φ(n)

Онлайн калькулятор вычисляет функцию Эйлера φ(n) — количество натуральных чисел от 1 до n, взаимно простых с n. Например, φ(12) = 4, потому что с 12 взаимно просты только 1, 5, 7 и 11. Для простого p ответ всегда равен p − 1, для составного — формула считается по разложению на простые множители.

Инструмент показывает результат за доли секунды, выводит каноническое разложение n на простые множители, расписывает формулу φ(n) = n × ∏(1 − 1/p), а для n ≤ 100 ещё и взаимно простые с n числа: до 20 первых и сколько их всего. Подходит студентам, преподавателям, олимпиадникам и тем, кто разбирается с алгоритмом RSA.

Функция Эйлера φ(n) (другие названия: тотиент, phi-функция, totient function) была введена Леонардом Эйлером в 1763 году. По определению φ(n) — число целых k в диапазоне 1 ≤ k ≤ n таких, что НОД(k, n) = 1, то есть взаимно простых с n.

Сегодня φ(n) — одна из основ модулярной арифметики и криптографии с открытым ключом: через неё вычисляют закрытый ключ RSA — и для шифрования, и для цифровой подписи. Она же возникает в задачах подсчёта примитивных корней, порядков элементов в группе (Z/nZ)*, числа несократимых дробей со знаменателем не больше n.

Если каноническое разложение числа n = p₁^a₁ × p₂^a₂ × … × p_k^a_k, то φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × … × (1 − 1/p_k). Эквивалентная запись через степени: φ(p^k) = p^k − p^(k−1) = p^(k−1)(p − 1).

Главные свойства, которые часто спрашивают на экзаменах: φ(1) = 1 (по определению), для простого p φ(p) = p − 1, мультипликативность φ(m × n) = φ(m) × φ(n) при НОД(m, n) = 1, тождество Гаусса ∑φ(d) = n по всем делителям d числа n, теорема Эйлера a^φ(n) ≡ 1 (mod n) при взаимно простых a и n.

В RSA выбирают два больших простых числа p и q, считают модуль n = p × q и φ(n) = (p − 1)(q − 1). Открытый ключ e — любое целое, взаимно простое с φ(n) (обычно e = 65537). Закрытый ключ d — мультипликативно обратный к e по модулю φ(n): d = e⁻¹ mod φ(n). Шифрование: c = m^e mod n. Расшифровка: m = c^d mod n — работает благодаря теореме Эйлера.

Безопасность RSA держится на трудности факторизации: зная n, нельзя за разумное время найти p, q и φ(n). Для 2048-битных модулей быстрого способа разложения не известно: для сравнения, 829-битное число RSA-250 разложили в 2020 году, и на это ушло около 2 700 лет работы одного процессорного ядра. Поэтому в учебной задаче с маленькими p, q калькулятор φ(n) показывает всё разложение, а в реальной криптографии — только знание простых даёт φ(n).