- Показатель числа по модулю
-
Показателем, или мультипликативным порядком, целого числа a по модулю m называется наименьшее положительное целое число , такое, что
Показатель определен только для чисел a, взаимно простых с модулем m, то есть для элементов группы обратимых элементов кольца вычетов по модулю m. При этом, если показатель числа a по модулю определен, то он является делителем значения функции Эйлера (следствие теоремы Лагранжа).
Чтобы показать зависимость показателя от a и m, его также обозначают , а если m фиксировано, то просто .
Содержание
Свойства
- , поэтому можно считать, что показатель задан на классе вычетов по модулю m.
- . В частности, и , где — функция Кармайкла, а — функция Эйлера.
- ; если , то
- Если p — простое число и , то — все решения сравнения .
- Если p — простое число, то — образующая группы .
- Если — количество классов вычетов с показателем , то . А для простых модулей даже .
- Если p — простое число, то группа вычетов циклична и потому, если , где g — образующая, , а k взаимно просто с , то . В общем случае для произвольного модуля m можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов.
Пример
Так как , но , , , то порядок числа 2 по модулю 15 равен 4.
Вычисление
Если известно разложение модуля m на простые множители и известно разложение чисел на простые множители, то показатель заданного числа a может быть найден за полиномиальное время от . Для вычисления достаточно найти разложение на множители функции Кармайкла и вычислить все для всех . Поскольку число делителей ограничено многочленом от , а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.
См. также
- Дискретное логарифмирование
- Функция Кармайкла
Литература
- Бухштаб Теория чисел
- Виноградов Теория чисел
Категория:- Теория чисел
Wikimedia Foundation. 2010.