Калькулятор первообразного корня

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

Что такое первообразный корень?

Первообразный корень по модулю n — это целое число g, степени которого порождают все целые числа, взаимно простые с n. Формально g является первообразным корнем mod n, если мультипликативный порядок g по модулю n равен функции Эйлера \(\varphi(n)\). Это означает, что набор

содержит ровно \(\varphi(n)\) целых чисел от 1 до n-1, которые взаимно просты с n. Первообразный корень, по сути, является генератором циклической группы \((\mathbb{Z}/n\mathbb{Z})^*\).

Краткий пример

Рассмотрим n = 7. Так как 7 — простое число, \(\varphi(7) = 6\). Проверим, является ли g = 3 первообразным корнем:

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

Степени дают {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}, что составляет все целые числа, взаимно простые с 7. Таким образом, 3 является первообразным корнем по модулю 7.

Когда существуют первообразные корни?

Первообразные корни по модулю n существуют тогда и только тогда, когда n имеет одну из следующих форм:

• n = 1, 2 или 4
• n = p^k, где p — нечетное простое число и k ≥ 1
• n = 2p^k, где p — нечетное простое число и k ≥ 1

Например, первообразные корни существуют для 7, 9, 11, 13, 14, 18, 23, 25, 27, 46, но не существуют для 8, 12, 15, 16, 20, 21, 24.

Как найти первообразные корни

1. Введите модуль: введите положительное целое число n (от 2 до 100 000) в поле ввода.
2. Рассчитайте: нажмите кнопку «Найти первообразные корни» или клавишу Enter.
3. Просмотрите все корни: вы увидите полный список первообразных корней вместе с функцией Эйлера и статистикой.
4. Изучите таблицу степеней: посмотрите, как наименьший первообразный корень порождает все взаимно простые вычеты.
5. Визуализируйте циклическую группу: для небольших модулей просмотрите анимированную схему, показывающую циклическую структуру.

Сколько первообразных корней имеет число n?

Если первообразные корни по модулю n существуют, их количество равно:

Например, для n = 13: \(\varphi(13) = 12\) и \(\varphi(12) = 4\), следовательно, существует ровно 4 первообразных корня по модулю 13 (это 2, 6, 7, 11).

Алгоритм проверки

Чтобы эффективно проверить, является ли g первообразным корнем по модулю n:

1. Вычислите \(\varphi(n)\), используя разложение n на простые множители.
2. Найдите все различные простые множители \(p_1, p_2, \ldots, p_k\) числа \(\varphi(n)\).
3. Для каждого простого множителя \(p_i\) проверьте условие: \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\).
4. Если ВСЕ проверки пройдены, то g является первообразным корнем.

Этот метод намного быстрее, чем вычисление всех степеней g, так как нам нужно проверить только \(k\) возведений в степень вместо \(\varphi(n)\).

Первообразные корни в криптографии

Обмен ключами Диффи-Хеллмана

Протокол Диффи-Хеллмана использует большое простое число p и первообразный корень g по модулю p. Алиса выбирает секретное число a и отправляет \(g^a \bmod p\). Боб выбирает секретное число b и отправляет \(g^b \bmod p\). Оба вычисляют общий секрет \(g^{ab} \bmod p\). Безопасность основана на том, что задача дискретного логарифмирования является вычислительно сложной.

Шифрование Эль-Гамаля

Эль-Гамаль также использует первообразный корень в качестве генератора. Открытый ключ — это \((p, g, g^x \bmod p)\), где x — закрытый ключ. Тот факт, что g порождает все элементы, гарантирует, что любое сообщение может быть зашифровано.

Цифровые подписи

DSA (алгоритм цифровой подписи) и родственные схемы используют первообразные корни в подгруппах \((\mathbb{Z}/p\mathbb{Z})^*\) для создания и проверки цифровых подписей.

Справочная таблица: наименьшие первообразные корни

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

Что такое первообразный корень по модулю n?

Первообразный корень по модулю n — это целое число g, такое что его степени \(g^1, g^2, \ldots, g^{\varphi(n)}\) при взятии по модулю n дают все целые числа, взаимно простые с n. Другими словами, g порождает всю мультипликативную группу \((\mathbb{Z}/n\mathbb{Z})^*\). Мультипликативный порядок g по модулю n равен значению функции Эйлера \(\varphi(n)\).

Для каких значений n существуют первообразные корни?

Первообразные корни по модулю n существуют тогда и только тогда, когда n равно 1, 2, 4, p^k или 2p^k, где p — нечетное простое число и k ≥ 1. Например, первообразные корни существуют для n = 7 (простое), n = 9 (3²), n = 14 (2×7), но НЕ существуют для n = 8, 12, 15 или 16.

Сколько первообразных корней имеет число n?

Если первообразные корни по модулю n существуют, то их количество равно \(\varphi(\varphi(n))\), где \(\varphi\) — функция Эйлера. Например, для n = 13 (простое), \(\varphi(13) = 12\) и \(\varphi(12) = 4\), следовательно, существует ровно 4 первообразных корня по модулю 13.

Почему первообразные корни важны в криптографии?

Первообразные корни фундаментальны для протокола обмена ключами Диффи-Хеллмана и системы шифрования Эль-Гамаля. В этих криптографических протоколах первообразный корень g по модулю большого простого числа p используется как генератор. Безопасность строится на сложности задачи дискретного логарифмирования: зная \(g^x \bmod p\), вычислительно трудно найти x.

Как проверить, является ли g первообразным корнем по модулю n?

Чтобы убедиться, что g — первообразный корень mod n: (1) Вычислите \(\varphi(n)\). (2) Найдите все простые множители \(p_1, p_2, \ldots, p_k\) числа \(\varphi(n)\). (3) Проверьте, что \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\) для каждого простого множителя \(p_i\). Если все условия выполнены, g является первообразным корнем. Это намного быстрее, чем возводить g во все степени.

Похожие инструменты