Первообразный корень

Первообразный корень — это целое число \( g \), которое является образующим элементом мультипликативной группы обратимых элементов кольца вычетов по модулю \( n \). Иными словами, для взаимно простого с \( n \) числа \( g \) его степени \( g^0, g^1, g^2, \dots, g^{\varphi(n)-1} \) (где \( \varphi(n) \) — функция Эйлера) образуют полную приведённую систему вычетов по модулю \( n \), то есть порождают все числа, взаимно простые с \( n \). Существование первообразного корня возможно не для всех натуральных \( n \), а только для модулей определённого вида: \( 2, 4, p^k, 2p^k \), где \( p \) — нечётное простое число, а \( k \ge 1 \).

Определение и основные свойства

Пусть \( n \) — натуральное число, большее 1. Обозначим через \( \mathbb{Z}_n^ \) мультипликативную группу обратимых элементов кольца вычетов \( \mathbb{Z}_n \). Порядок этой группы равен \( \varphi(n) \). Элемент \( g \in \mathbb{Z}_n^ \) называется первообразным корнем по модулю \( n \), если его порядок в группе \( \mathbb{Z}_n^* \) равен \( \varphi(n) \). Это означает, что \( g^{\varphi(n)} \equiv 1 \pmod{n} \), и для любого меньшего положительного показателя \( m < \varphi(n) \) сравнение \( g^m \equiv 1 \pmod{n} \) не выполняется.

Из этого определения вытекают ключевые свойства:

• Все степени \( g^0, g^1, \dots, g^{\varphi(n)-1} \) различны по модулю \( n \) и взаимно просты с \( n \).
• Любое число \( a \), взаимно простое с \( n \), может быть единственным образом представлено в виде \( a \equiv g^k \pmod{n} \), где \( 0 \le k < \varphi(n) \). Показатель \( k \) называется индексом (или дискретным логарифмом) числа \( a \) по основанию \( g \).
• Если \( g \) — первообразный корень по модулю \( n \), то и \( g^{-1} \) (обратный элемент по модулю \( n \)) также является первообразным корнем.

Теорема существования

Не для всякого модуля \( n \) существует первообразный корень. Теорема Гаусса (из «Арифметических исследований», 1801) утверждает, что первообразные корни существуют только для модулей следующих видов:

• \( n = 2 \);
• \( n = 4 \);
• \( n = p^k \), где \( p \) — нечётное простое число, \( k \ge 1 \);
• \( n = 2p^k \), где \( p \) — нечётное простое число, \( k \ge 1 \).

Для всех остальных натуральных чисел \( n \) (например, \( n = 8, 12, 15, 20, 24 \) и т.д.) первообразных корней не существует. Причина — в структуре группы \( \mathbb{Z}_n^* \): если \( n \) имеет два различных нечётных простых делителя или делится на 8, группа не является циклической.

Примеры существования и несуществования

• По модулю 2: \( \varphi(2)=1 \), число 1 является первообразным корнем (так как \( 1^1 \equiv 1 \)).
• По модулю 4: \( \varphi(4)=2 \), первообразный корень — 3 (так как \( 3^1=3 \), \( 3^2=9 \equiv 1 \)).
• По модулю 7 (простое число): \( \varphi(7)=6 \). Первообразные корни: 3 и 5. Проверка: \( 3^1=3 \), \( 3^2=9 \equiv 2 \), \( 3^3=27 \equiv 6 \), \( 3^4=81 \equiv 4 \), \( 3^5=243 \equiv 5 \), \( 3^6=729 \equiv 1 \). Все ненулевые вычеты по модулю 7 получены.
• По модулю 8: \( \varphi(8)=4 \), но группа \( \mathbb{Z}_8^* = \{1,3,5,7\} \) изоморфна \( \mathbb{Z}_2 \times \mathbb{Z}_2 \) и не является циклической. Ни одно число не имеет порядка 4: 1 — порядок 1, 3 — порядок 2 (так как \( 3^2=9 \equiv 1 \)), 5 — порядок 2, 7 — порядок 2. Первообразных корней нет.
• По модулю 15: \( \varphi(15)=8 \), группа \( \mathbb{Z}_{15}^* \) изоморфна \( \mathbb{Z}_2 \times \mathbb{Z}_4 \) и не является циклической. Первообразных корней нет.

Количество первообразных корней

Если для модуля \( n \) первообразные корни существуют, то их количество равно \( \varphi(\varphi(n)) \). Это следует из того, что если \( g \) — первообразный корень, то все первообразные корни — это числа вида \( g^m \), где \( m \) взаимно просто с \( \varphi(n) \). Действительно, порядок элемента \( g^m \) равен \( \varphi(n) / \gcd(m, \varphi(n)) \). Чтобы он равнялся \( \varphi(n) \), необходимо и достаточно, чтобы \( \gcd(m, \varphi(n)) = 1 \). Количество таких \( m \) от 1 до \( \varphi(n)-1 \) равно \( \varphi(\varphi(n)) \).

Примеры

• По модулю 7: \( \varphi(7)=6 \), \( \varphi(6)=2 \). Действительно, первообразных корней два: 3 и 5.
• По модулю 11: \( \varphi(11)=10 \), \( \varphi(10)=4 \). Первообразные корни: 2, 6, 7, 8 (всего 4).
• По модулю 9: \( \varphi(9)=6 \), \( \varphi(6)=2 \). Первообразные корни: 2 и 5. Проверка: \( 2^1=2 \), \( 2^2=4 \), \( 2^3=8 \), \( 2^4=16 \equiv 7 \), \( 2^5=32 \equiv 5 \), \( 2^6=64 \equiv 1 \). Аналогично для 5.

Поиск первообразных корней

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

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

Пусть дано число \( g \), взаимно простое с \( n \). Чтобы проверить, является ли \( g \) первообразным корнем по модулю \( n \), необходимо:

1. Вычислить \( \varphi(n) \).
2. Найти все различные простые делители \( q_1, q_2, \dots, q_k \) числа \( \varphi(n) \).
3. Для каждого \( q_i \) проверить, что \( g^{\varphi(n)/q_i} \not\equiv 1 \pmod{n} \).

Если ни одно из этих сравнений не даёт 1, то \( g \) — первообразный корень. В противном случае — нет.

Этот критерий основан на том, что порядок элемента делит \( \varphi(n) \), и если он не является делителем ни одного из чисел \( \varphi(n)/q_i \), то он равен \( \varphi(n) \).

Пример проверки

Проверим, является ли 2 первообразным корнем по модулю 13. \( \varphi(13)=12 \). Простые делители 12: 2 и 3. Вычисляем:

• \( 2^{12/2} = 2^6 = 64 \equiv 12 \pmod{13} \) (не 1).
• \( 2^{12/3} = 2^4 = 16 \equiv 3 \pmod{13} \) (не 1).

Условия выполнены, значит 2 — первообразный корень по модулю 13. Действительно, степени двойки дают все ненулевые вычеты: 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1.

Применение

Первообразные корни находят применение в различных областях математики и криптографии.

Криптография

• Протокол Диффи — Хеллмана: основан на задаче дискретного логарифмирования. Стороны выбирают большое простое число \( p \) и первообразный корень \( g \) по модулю \( p \). Затем каждая сторона генерирует секретный ключ \( a \) и отправляет другой стороне \( g^a \mod p \). Общий секрет вычисляется как \( (g^a)^b = (g^b)^a = g^{ab} \mod p \). Без знания \( a \) или \( b \) вычислить \( g^{ab} \) сложно (предполагается вычислительная стойкость).
• Схема Эль-Гамаля: асимметричная криптосистема, использующая первообразный корень для генерации открытого ключа. Открытый ключ: \( (p, g, y = g^x \mod p) \), где \( x \) — секретный ключ.
• Генерация псевдослучайных чисел: линейные конгруэнтные генераторы и другие методы могут использовать первообразные корни для обеспечения максимального периода последовательности.

Теория чисел

• Символ Лежандра и квадратичные вычеты: первообразные корни позволяют классифицировать числа по их индексам. Например, число \( a \) является квадратичным вычетом по модулю простого \( p \) тогда и только тогда, когда его индекс по основанию первообразного корня чётен.
• Построение конечных полей: мультипликативная группа любого конечного поля \( \mathbb{F}_{p^k} \) циклическая, и её образующий элемент является первообразным корнем поля. Это используется в алгебраической теории кодирования и криптографии на эллиптических кривых.
• Дискретное логарифмирование: задача нахождения индекса числа по заданному первообразному корню лежит в основе многих криптографических протоколов. Сложность этой задачи для больших простых чисел является основой стойкости ряда криптосистем.

Другие области

• Циклические коды: в теории кодирования первообразные корни используются для построения циклических кодов, таких как коды БЧХ (Боуза — Чоудхури — Хоквингема) и Рида — Соломона. Корни порождающего многочлена выбираются как степени первообразного корня поля.
• Алгоритмы быстрого преобразования Фурье: в некоторых реализациях БПФ над конечными полями используются первообразные корни для вычисления корней из единицы.

Интересные факты

• Наименьший первообразный корень по модулю простого числа \( p \) часто бывает небольшим. Для \( p = 2 \) это 1, для \( p = 3 \) — 2, для \( p = 5 \) — 2, для \( p = 7 \) — 3, для \( p = 11 \) — 2, для \( p = 13 \) — 2, для \( p = 17 \) — 3, для \( p = 19 \) — 2, для \( p = 23 \) — 5. Однако для некоторых простых чисел наименьший первообразный корень может быть довольно большим (например, для \( p = 191 \) это 19, для \( p = 409 \) — 21).
• Гипотеза Артина (1927) утверждает, что для любого целого числа \( a \), не равного \(-1\) и не являющегося полным квадратом, существует бесконечно много простых чисел \( p \), для которых \( a \) является первообразным корнем по модулю \( p \). Эта гипотеза не доказана, но имеет многочисленные частичные результаты.
• Первообразные корни тесно связаны с циклическими группами. Группа \( \mathbb{Z}_n^* \) циклическая тогда и только тогда, когда \( n \) имеет вид \( 2, 4, p^k, 2p^k \). Это было доказано Гауссом.

Источники

• Гаусс К. Ф. «Арифметические исследования» (1801).
• Виноградов И. М. «Основы теории чисел» (1952).
• Айерлэнд К., Роузен М. «Классическое введение в современную теорию чисел» (1982).
• Молдовян Н. А. «Теоретико-числовые методы в криптографии» (2005).
• Шнайер Б. «Прикладная криптография» (1996).