Показатель числа по модулю

Показателем, или мультипликативным порядком, целого числа a по модулю m называется наименьшее положительное целое число $\ell$, такое, что

$a^\ell \equiv 1\pmod m.$

Показатель определен только для чисел a, взаимно простых с модулем m, то есть для элементов группы обратимых элементов кольца вычетов по модулю m. При этом, если показатель числа a по модулю определен, то он является делителем значения функции Эйлера $\varphi(m)$ (следствие теоремы Лагранжа).

Чтобы показать зависимость показателя $\ell$ от a и m, его также обозначают $P_m(a)$, а если m фиксировано, то просто $P(a)$.

Свойства

• $a\equiv b\pmod m\Rightarrow P(a)=P(b)$, поэтому можно считать, что показатель задан на классе вычетов $\bar{a}$ по модулю m.
• $a^n\equiv 1\pmod m\Rightarrow P(a)\mid n$. В частности, $P(a)\mid\lambda(m)$ и $P(a)\mid\varphi(m)$, где $\lambda(m)$ — функция Кармайкла, а $\varphi(m)$ — функция Эйлера.
• $a^t\equiv a^s\pmod m \Leftrightarrow t\equiv s\pmod{P(a)}.$
• $P(a^s)\mid P(a)$; если $\gcd(s,P(a))=1$, то $P(a^s)=P(a).$
• Если p — простое число и $P(a)=k$, то $a,\ldots,a^k$ — все решения сравнения $x^k\equiv 1\pmod p$.
• Если p — простое число, то $P(a)=p-1\Leftrightarrow a$ — образующая группы $\mathbb{Z}_p$.
• Если $\psi(k)$ — количество классов вычетов с показателем $k$, то $\sum\limits_{k\mid\varphi(m)}\psi(k)=\varphi(m)$. А для простых модулей даже $\psi(k)=\varphi(k)$.
• Если p — простое число, то группа вычетов $\mathbb{Z}_p^{\times}$ циклична и потому, если $a=g^{dk}$, где g — образующая, $d\mid p-1$, а k взаимно просто с $p-1$, то $P(a)=\frac{p-1}{d}$. В общем случае для произвольного модуля m можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов$\mathbb{Z}_m^{\times}$.

Пример

Так как $2^4\equiv 1\pmod{15}$, но $2^1\not\equiv 1\pmod{15}$, $2^2\not\equiv 1\pmod{15}$, $2^3\not\equiv 1\pmod{15}$, то порядок числа 2 по модулю 15 равен 4.

Вычисление

Если известно разложение модуля m на простые множители $p_j$ и известно разложение чисел $p_j-1$ на простые множители, то показатель заданного числа a может быть найден за полиномиальное время от $\ln m$. Для вычисления достаточно найти разложение на множители функции Кармайкла $\lambda(m)$ и вычислить все $a^d \mod m$ для всех $d\mid \lambda (m)$. Поскольку число делителей ограничено многочленом от $\ln m$, а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.

См. также

• Дискретное логарифмирование
• Функция Кармайкла

Литература

• Бухштаб Теория чисел
• Виноградов Теория чисел