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

Дано: модуль $n = 41$, кандидаты 2, 3, 5 и 6. Найти: наименьший первообразный корень по модулю 41.

Модуль простой, поэтому первообразный корень заведомо существует, а на проверку одного кандидата уходит не сорок возведений в степень, а всего два. Ответ: наименьший первообразный корень по модулю 41 равен 6, его порядок равен $\varphi(41) = 40$, а всего таких корней по этому модулю 16. Калькулятор сверху прогоняет ту же проверку для любого модуля до 200 и рисует, где замыкается цикл степеней.

Решение по шагам

Дано. $n = 41$. Найти: наименьшее $g$, у которого степени $g^1, g^2, \dots, g^{40}$ пробегают все ненулевые вычеты по модулю 41.

Шаг 1. Считаем функцию Эйлера. Число 41 простое, значит, обратим каждый вычет от 1 до 40:

$$\varphi(41) = 41 - 1 = 40.$$

Порядок элемента $\operatorname{ord}(g)$ - это наименьшая степень, дающая остаток 1. По теореме Лагранжа он всегда делит $\varphi(n)$, а первообразный корень - это элемент, у которого порядок равен $\varphi(n)$ целиком.

Шаг 2. Раскладываем функцию Эйлера на простые множители.

$$40 = 2^3 \cdot 5, \qquad q \in \{2,\ 5\}.$$

Нужны только сами простые делители, кратности не играют роли: проверять 4 и 8 вместо двойки незачем. Если модуль большой, разложение удобно получать перебором простых множителей.

Шаг 3. Выписываем контрольные показатели. Их ровно столько, сколько простых делителей: $40 / 2 = 20$ и $40 / 5 = 8$. Критерий выглядит так:

$$g^{20} \not\equiv 1 \pmod{41} \quad \text{и} \quad g^{8} \not\equiv 1 \pmod{41}.$$

Если хотя бы одна из двух степеней даёт единицу, порядок кандидата меньше сорока, и он отпадает.

Шаг 4. Кандидат $g = 2$. Считаем обе степени через квадраты: $2^8 = 256 = 6 \cdot 41 + 10$, то есть $2^8 \equiv 10$ - первое условие выполнено. Но $2^{10} = 1024 = 24 \cdot 41 + 40 \equiv -1$, откуда $2^{20} \equiv (-1)^2 \equiv 1$. Двойка отпадает, её порядок равен 20.

Шаг 5. Кандидат $g = 3$. Здесь всё обрывается на первом же шаге: $3^4 = 81 \equiv 40 \equiv -1$, значит $3^8 \equiv 1 \pmod{41}$. Тройка отпадает, её порядок равен 8 - она крутится всего по восьми вычетам из сорока.

Шаг 6. Четвёрку пропускаем без счёта. Полный квадрат никогда не бывает первообразным корнем по нечётному простому модулю: для $g = a^2$ имеем $g^{(p-1)/2} = a^{p-1} \equiv 1$ по малой теореме Ферма. Так что 4, 9, 16, 25 и 36 из перебора вычёркиваются сразу.

Шаг 7. Кандидат $g = 5$. $5^4 = 625 = 15 \cdot 41 + 10 \equiv 10$, дальше $5^5 \equiv 10 \cdot 5 = 50 \equiv 9$ и $5^{10} \equiv 9^2 = 81 \equiv -1$. Значит, $5^{20} \equiv 1$, и пятёрка отпадает с порядком 20.

Шаг 8. Кандидат $g = 6$. Поднимаемся по квадратам:

$$\begin{aligned} 6^2 &= 36, \\ 6^4 &\equiv 36^2 = 1296 = 31 \cdot 41 + 25 \equiv 25, \\ 6^8 &\equiv 25^2 = 625 \equiv 10 \not\equiv 1, \\ 6^5 &\equiv 25 \cdot 6 = 150 \equiv 27, \\ 6^{10} &\equiv 27^2 = 729 \equiv 32, \\ 6^{20} &\equiv 32^2 = 1024 \equiv 40 \equiv -1 \not\equiv 1. \end{aligned}$$

Обе контрольные степени отличны от единицы, поэтому порядок шестёрки не может быть собственным делителем сорока - он равен сорока.

Ответ: наименьший первообразный корень по модулю 41 равен $g = 6$.

Формула и откуда она берётся

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

$$\operatorname{ord}_n(g) = \varphi(n) \iff g^{\varphi(n)/q} \not\equiv 1 \pmod{n} \ \text{ для всех простых } q \mid \varphi(n).$$

Почему этого достаточно? Пусть порядок $d$ меньше $\varphi(n)$. По теореме Лагранжа он делит $\varphi(n)$, причём делит строго, значит, частное $\varphi(n)/d$ имеет хотя бы один простой делитель $q$. Тогда $d$ делит $\varphi(n)/q$, и степень $g^{\varphi(n)/q}$ обязана дать единицу - как раз то, что мы ловим. Обратное очевидно: если порядок равен $\varphi(n)$, никакая меньшая степень единицы не даёт.

Отсюда и экономия. Наивная проверка «посчитать все степени, пока не вернётся 1» требует до $\varphi(n)$ умножений, критерий - столько возведений в степень, сколько у $\varphi(n)$ разных простых делителей. Для модуля 41 это два возведения вместо сорока, и каждое делается бинарным алгоритмом за десяток умножений.

Сколько корней и стоит ли надеяться на двойку

Если первообразный корень $g$ найден, все остальные получаются как $g^k$, где $k$ взаимно просто с $\varphi(n)$. Поэтому их количество равно $\varphi(\varphi(n))$, у нас - $\varphi(40) = 16$. Это почти 40 процентов всех вычетов, так что перебор снизу обычно заканчивается на первом десятке: по модулю 41 корнями служат 6, 7, 11, 12, 13, 15, 17, 19 и ещё восемь чисел.

Но гарантии, что подойдёт двойка, нет никакой, и на этом чаще всего спотыкаются. По модулям 11, 13, 19, 29, 37, 101 наименьший первообразный корень действительно равен 2, по модулю 41 - уже 6, а по модулю 191 - целых 19. Ничего кроме перебора с критерием тут не предложить: формулы для наименьшего корня не существует, есть только оценки сверху. Проверить очередного кандидата на взаимную простоту с модулем помогает алгоритм Евклида, а для простого модуля это условие выполняется автоматически.

Когда первообразного корня не существует

Для составного модуля вопрос не сводится к перебору: корня может не быть вовсе. Первообразный корень существует ровно по модулям

$$n = 1,\ 2,\ 4,\ p^k,\ 2p^k, \qquad p \ \text{- нечётное простое}.$$

Возьмём $n = 8$: обратимые вычеты 1, 3, 5, 7, их четыре, то есть $\varphi(8) = 4$. Но $3^2 = 9 \equiv 1$, $5^2 = 25 \equiv 1$, $7^2 = 49 \equiv 1$ - порядок каждого не больше двух, до четвёрки не дотягивает никто. А вот по модулю $18 = 2 \cdot 3^2$ корень есть: $\varphi(18) = 6$, и степени пятёрки дают 5, 7, 17, 13, 11, 1 - все шесть обратимых вычетов. Так что перед перебором сначала проверь модуль на простоту или разложи его и убедись, что он нужного вида.

Таблица степеней и индексы

Когда корень найден, из него строят таблицу степеней - по сути, таблицу логарифмов в конечном поле. Для $g = 6$ и модуля 41 начало выглядит так:

Обратная функция называется индексом, или дискретным логарифмом: $\operatorname{ind}(a)$ - тот показатель $k$, при котором $6^k \equiv a$. Индексы превращают умножение в сложение по модулю 40: $\operatorname{ind}(2) = 26$, $\operatorname{ind}(3) = 15$, и сумма $26 + 15 = 41 \equiv 1 \pmod{40}$ ровно совпадает с $\operatorname{ind}(6) = 1$, потому что $2 \cdot 3 = 6$.

Работает это и на корнях. Пусть надо решить $x^3 \equiv 37 \pmod{41}$. По таблице $\operatorname{ind}(37) = 32$, значит $3 \operatorname{ind}(x) \equiv 32 \pmod{40}$, откуда $\operatorname{ind}(x) = 24$ и $x = 6^{24} \equiv 16$. Проверка: $16^3 = 4096 = 99 \cdot 41 + 37$. Обратный ход - от $a$ к индексу - вычислительно тяжёл: на этом стоят обмен ключами Диффи-Хеллмана и подпись Эль-Гамаля, а быстрые методы вроде алгоритма Полига-Хеллмана работают, лишь когда $\varphi(n)$ раскладывается на мелкие множители.

Частые ошибки

• Раскладывают на множители сам модуль $n$, а не $\varphi(n)$. В критерий входят простые делители порядка группы, а не модуля: для 41 это делители сорока.
• Берут все делители $\varphi(n)$, а не простые. Проверка $g^{40/4}$ и $g^{40/8}$ - лишняя работа, которая к тому же путает: для двойки среди делителей достаточно одного показателя 20.
• Забывают про условие $\gcd(g, n) = 1$ для составного модуля. Число, имеющее с модулем общий делитель, не даёт единицу ни в какой степени, и порядок у него не определён.
• Считают степени наивно, перемножая по одному разу. При модуле в несколько сотен это терпимо, при криптографическом - нет: нужно возведение по двоичной записи показателя.
• Останавливаются, как только одна из проверок дала не единицу. Условие должно выполняться для всех простых делителей сразу: у тройки по модулю 41 первая проверка проходит, а вторая валит.
• Путают первообразный корень с квадратным корнем по модулю или с корнем многочлена. Здесь речь о порождающем элементе группы, а не о решении уравнения.

FAQ

Чем порядок элемента отличается от первообразного корня? Порядок есть у каждого обратимого вычета: это наименьший показатель, возвращающий остаток 1. Первообразный корень - частный случай, когда порядок дотянул до максимума $\varphi(n)$. Скажем, по модулю 41 у тройки порядок 8, у двойки 20, а у шестёрки 40, и только шестёрка считается первообразным корнем.

Обязательно ли начинать перебор с двойки? Да, если нужен именно наименьший корень: кандидаты проверяются подряд, 2, 3, 5, 6 и так далее, а полные квадраты и другие степени можно пропускать. Если корень нужен любой, в криптографии часто берут простое вида $p = 2q + 1$: тогда у $\varphi(p) = 2q$ всего два простых делителя, и проверка занимает две операции.

Что делать, если $\varphi(n)$ не раскладывается? Это и есть узкое место метода: критерий требует знать простые делители $\varphi(n)$. Для больших модулей поступают наоборот - сначала конструируют простое число с заранее известным разложением $p - 1$, а потом ищут корень.

Сколько первообразных корней по простому модулю $p$? Ровно $\varphi(p-1)$ штук. Для $p = 41$ это $\varphi(40) = 16$, для $p = 101$ уже $\varphi(100) = 40$. Найдя один корень, остальные получают как $g^k$ с $\gcd(k, \varphi(n)) = 1$, заново перебирать не нужно.

Коротко

1. Проверь, что модуль имеет вид 2, 4, $p^k$ или $2p^k$: иначе первообразного корня не существует.
2. Посчитай $\varphi(n)$ (для простого $n$ это $n - 1$) и разложи её на простые множители: $\varphi(41) = 40 = 2^3 \cdot 5$.
3. Для каждого простого делителя $q$ посчитай $g^{\varphi(n)/q} \bmod n$; здесь это показатели 20 и 8.
4. Единица хотя бы в одной проверке - кандидат отпадает: так выбывают 2 (порядок 20), 3 (порядок 8) и 5 (порядок 20).
5. Ответ: $g = 6$ - наименьший первообразный корень по модулю 41, всего их $\varphi(40) = 16$.