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

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

Функция Эйлера — ключевой инструмент в теории чисел и криптографии (RSA). Калькулятор показывает результат, разложение на множители и список взаимно простых чисел.

Если n = p₁^a₁ × p₂^a₂ × ..., то φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × ... Для простого p: φ(p) = p − 1. Для степени простого: φ(p^k) = p^k − p^(k−1).

Свойства: φ(1) = 1. Для простого p: φ(p) = p−1. Мультипликативность: φ(m×n) = φ(m)×φ(n) при НОД(m,n) = 1. Теорема Эйлера: a^φ(n) ≡ 1 (mod n) при НОД(a,n) = 1.

Алгоритм RSA: выбираем два простых p и q, вычисляем n = p×q и φ(n) = (p−1)(q−1). Открытый ключ e взаимно прост с φ(n), закрытый d = e⁻¹ mod φ(n).

Безопасность RSA основана на сложности разложения n на множители. Если n = 2048 бит, нахождение p и q (и φ(n)) — задача, неразрешимая за разумное время.