Математика. Понятие показателя. Простейшие свойства. Нахождение показателей. Первообразные корни.

Первообразным корнем по модулю  (primitive root modulo ) называется такое число , что все его степени по модулю  пробегают по всем числам, взаимно простым с . Математически это формулируется таким образом: если  является первообразным корнем по модулю , то для любого целого  такого, что , найдётся такое целое , что .

В частности, для случая простого  степени первообразного корня пробегают по всем числам от  до .

Существование

Первообразный корень по модулю  существует тогда и только тогда, когда  является либо степенью нечётного простого, либо удвоенной степенью простого, а также в случаях , , .

Эта теорема (которая была полностью доказана Гауссом в 1801 г.) приводится здесь без доказательства.

Связь с функцией Эйлера

Пусть  - первообразный корень по модулю . Тогда можно показать, что наименьшее число , для которого  (т.е.  — показатель  (multiplicative order)), равно . Более того, верно и обратное, и этот факт будет использован нами ниже в алгоритме нахождения первообразного корня.

Кроме того, если по модулю  есть хотя бы один первообразный корень, то всего их  (т.к. циклическая группа с  элементами имеет  генераторов).

Алгоритм нахождения первообразного корня

Наивный алгоритм потребует для каждого тестируемого значения   времени, чтобы вычислить все его степени и проверить, что они все различны. Это слишком медленный алгоритм, ниже мы с помощью нескольких известных теорем из теории чисел получим более быстрый алгоритм.

Выше была приведена теорема о том, что если наименьшее число , для которого  (т.е.  — показатель ), равно , то  — первообразный корень. Так как для любого числа , взаимно простого с , выполняется теорема Эйлера (), то чтобы проверить, что  первообразный корень, достаточно проверить, что для всех чисел , меньших , выполнялось . Однако пока это слишком медленный алгоритм.

Из теоремы Лагранжа следует, что показатель любого числа по модулю  является делителем . Таким образом, достаточно проверить, что для всех собственных делителей  выполняется . Это уже значительно более быстрый алгоритм, однако можно пойти ещё дальше.

Факторизуем число . Докажем, что в предыдущем алгоритме достаточно рассматривать в качестве  лишь числа вида . Действительно, пусть  — произвольный собственный делитель . Тогда, очевидно, найдётся такое , что , т.е. . Однако, если бы , то мы получили бы:

т.е. всё равно среди чисел вида  нашлось бы то, для которого условие не выполнилось, что и требовалось доказать.

Таким образом, алгоритм нахождения первообразного корня такой. Находим , факторизуем его. Теперь перебираем все числа , и для каждого считаем все величины . Если для текущего  все эти числа оказались отличными от , то это  и является искомым первообразным корнем.

Время работы алгоритма (считая, что у числа  имеется  делителей, а возведение в степень выполняется алгоритмом Бинарного возведения в степень, т.е. за ) равно  плюс время факторизации числа , где  — результат, т.е. значение искомого первообразного корня.

Про скорость роста первообразных корней с ростом  известны лишь приблизительные оценки. Известно, что первообразные корни — сравнительно небольшие величины. Одна из известных оценок — оценка Шупа (Shoup), что, в предположении истинности гипотезы Римана, первообразный корень есть .