WikiSort.ru - Не сортированное

Показателем, или мультипликативным порядком, целого числа ${\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}$ , а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.

Приложения

См. также

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

Примечания

Литература

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