Порядок числа по модулю

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

${\displaystyle a^{\ell }\equiv 1{\pmod {m}}.}$

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

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

Свойства

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

Пример

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

Вычисление

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

Приложения

Характеры Дирихле

Характер Дирихле ${\displaystyle \chi }$ по модулю ${\displaystyle m}$ определяется обязательными соотношениями ${\displaystyle \chi (ab)=\chi (a)\chi (b)}$ и ${\displaystyle \chi (a)=\chi (a+m)}$. Чтобы эти соотношения выполнялись, необходимо, чтобы ${\displaystyle \chi (a)}$ был равен какому-либо комплексному корню из единицы степени ${\displaystyle P_{m}(a)}$.

См. также

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