Калькулятор функции Эйлера

Добро пожаловать в Калькулятор функции Эйлера — комплексный инструмент теории чисел, который вычисляет φ(n) (фи-функцию Эйлера) с пошаговым разложением на простые множители, интерактивной визуализацией сетки взаимно простых чисел и углубленным анализом. Изучаете ли вы абстрактную алгебру, готовитесь к математическим олимпиадам, работаете над криптографией RSA или исследуете модульную арифметику, этот калькулятор обеспечивает профессиональные вычисления с богатым образовательным контентом.

Что такое функция Эйлера?

Функция Эйлера φ(n), также известная как фи-функция Эйлера, подсчитывает количество положительных целых чисел от 1 до n, которые являются взаимно простыми с n. Два числа являются взаимно простыми, когда их наибольший общий делитель (НОД) равен 1.

Например, φ(12) = 4, потому что ровно четыре числа — 1, 5, 7 и 11 — взаимно просты с 12 среди целых чисел от 1 до 12.

Формула произведения

Самый эффективный способ вычислить φ(n) использует разложение на простые множители числа n. Если \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\), то:

Это означает, что мы умножаем n на \((1 - 1/p)\) для каждого отличного простого множителя p числа n. Степени не имеют значения — только уникальные простые числа.

Ключевые свойства

Теорема Эйлера

Теорема Эйлера — это ключевой результат, который делает функцию тотиента крайне важной в криптографии:

Это обобщает малую теорему Ферма (которая является частным случаем, когда n — простое число). Она формирует математическую основу шифрования RSA.

Как пользоваться этим калькулятором

1. Введите целое положительное число: Введите любое значение от 1 до 1 000 000 в поле ввода.
2. Используйте быстрые примеры: Нажмите на кнопки примеров, чтобы попробовать классические значения, такие как простые числа, составные числа или полупростые числа в стиле RSA.
3. Просмотрите результаты: Калькулятор покажет φ(n), разложение на простые множители, соотношение взаимно простых чисел и обнаруженные свойства.
4. Исследуйте сетку взаимно простых чисел: Для n ≤ 400 посмотрите, какие числа взаимно просты с n в анимированной визуальной сетке.
5. Изучите график тренда: Посмотрите, как φ(k) меняется для k от 1 до min(n, 100).

Связь с шифрованием RSA

В криптографии RSA функция Эйлера играет центральную роль:

1. Выбираются два больших простых числа p и q. Вычисляется n = p × q.
2. Вычисляется φ(n) = (p−1)(q−1).
3. Выбирается открытая экспонента e, такая что gcd(e, φ(n)) = 1.
4. Вычисляется закрытая экспонента d, такая что e × d ≡ 1 (mod φ(n)).

Безопасность RSA основана на сложности вычисления φ(n) без знания факторизации n. Если бы злоумышленник мог эффективно вычислить φ(n), он смог бы взломать RSA.

Общие значения φ(n)

Часто задаваемые вопросы

Что такое функция Эйлера?

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

Как рассчитать функцию Эйлера?

Чтобы рассчитать φ(n): (1) Найдите разложение n на простые множители. (2) Примените формулу произведения: φ(n) = n × ∏(1 − 1/p) для каждого отличного простого множителя p числа n. Например, φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Для простого p, φ(p) = p−1. Для степени простого числа p^k, φ(p^k) = p^k − p^(k−1).

Почему функция Эйлера важна в шифровании RSA?

В шифровании RSA модуль n = p × q является произведением двух больших простых чисел. Тотиент φ(n) = (p−1)(q−1) используется для вычисления закрытого ключа: экспонента дешифрования d должна удовлетворять условию e × d ≡ 1 (mod φ(n)), где e — открытая экспонента шифрования. Без знания φ(n), что требует факторизации n, вычисление d практически невозможно.

Что такое теорема Эйлера и как она связана с функцией тотиента?

Теорема Эйлера утверждает, что если a и n взаимно просты, то a^φ(n) ≡ 1 (mod n). Это обобщение малой теоремы Ферма (которая применима, когда n простое). Она фундаментальна в модульной арифметике и криптографии, обеспечивая математическую основу для шифрования RSA и эффективного возведения в степень по модулю.

Каковы основные свойства функции Эйлера?

Основные свойства включают: (1) φ(1) = 1. (2) Для простого p: φ(p) = p−1. (3) Для степени простого числа p^k: φ(p^k) = p^(k−1)(p−1). (4) Мультипликативность: если gcd(m,n) = 1, то φ(m×n) = φ(m)×φ(n). (5) Сумма по делителям: Σ φ(d) = n для всех делителей d числа n. (6) φ(n) всегда четно для n > 2.

Что значит, когда два числа взаимно просты?

Два целых числа a и b называются взаимно простыми, если их наибольший общий делитель равен 1, что означает отсутствие у них общих простых множителей. Например, 8 и 15 взаимно просты, так как gcd(8,15) = 1, хотя ни одно из них не является простым. Функция Эйлера φ(n) точно подсчитывает, сколько целых чисел от 1 до n взаимно просты с n.

Дополнительные ресурсы

• Функция Эйлера — Википедия
• Криптосистема RSA — Википедия
• Теорема Эйлера — Википедия