Примитивный корень простого числа n по модулю n
Для простого числа 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
Простое решение - попробовать все числа от 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 и многому другому, см. Полный курс подготовки к собеседованию .