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

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

[math]\displaystyle{ a^\ell\equiv 1\pmod m. }[/math]

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

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

Свойства

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

Пример

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

Вычисление

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

Приложения

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

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

См. также

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

Литература

• Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966.
• Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.