Примитивный корень простого числа n по модулю n

Опубликовано: 20 Января, 2022

Для простого числа n задача состоит в том, чтобы найти его первообразный корень по модулю n. Первоначальный корень простого числа n - это целое число r между [1, n-1], такое, что значения r ^ x (mod n), где x находится в диапазоне [0, n-2], различны. Верните -1, если n - непростое число.

Примеры:

 Ввод: 7
Выход: наименьший первообразный корень = 3
Пояснение: n = 7
3 ^ 0 (мод 7) = 1
3 ^ 1 (мод 7) = 3
3 ^ 2 (мод 7) = 2
3 ^ 3 (мод 7) = 6
3 ^ 4 (мод 7) = 4
3 ^ 5 (мод 7) = 5

Ввод: 761
Выход: наименьший первообразный корень = 6
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Простое решение - попробовать все числа от 2 до n-1. Для каждого числа r вычислите значения r ^ x (mod n), где x находится в диапазоне [0, n-2]. Если все эти значения различны, верните r, иначе продолжите для следующего значения r. Если все значения r проверены, верните -1.

Эффективное решение основано на приведенных ниже фактах.
Если порядок мультипликативности числа r по модулю n равен функции Totient Эйлера Φ (n) (обратите внимание, что функция Totient Эйлера для простого n равна n-1), то это примитивный корень.

 1- Функция Эйлера Тоиэнт phi = n-1 [Предполагается, что n - простое число]
1- Найдите все простые множители фи.
2- Рассчитайте все мощности для дальнейшего расчета 
   используя (фи / простые множители) один за другим.
3- Проверить все пронумерованные для всех степеней от i = 2 
   к n-1, т.е. (i ^ степени) по модулю n.
4- Если это 1, то «i» не является первообразным корнем n.
5- Если он никогда не равен 1, верните i ;.

Хотя у простого числа может быть несколько примитивных корней, нас интересует только самый маленький из них. Если вы хотите найти все корни, продолжайте процесс до p-1 вместо того, чтобы разбивать на поиск первого примитивного корня.

Выход:

 Наименьший первообразный корень из 761 равен 6

Авторы этой статьи - Нитиш Кумар и Сахил Чхабра (акку). Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью, используя write.geeksforgeeks.org, или отправить свою статью по электронной почте: deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

РЕКОМЕНДУЕМЫЕ СТАТЬИ