Найти первообразные корни по модулю. Нахождение первообразных корней по простому модулю

В настоящем пункте будем рассматривать число n , причем n -1= * - каноническое разложение на простые сомножители.

Теорема

O n (a )=n -1 1) a n -1 ≡1(mod n );

2) , 1(mod n ).

Доказательство:

Пусть O n (a )=n -1. Тогда (1) выполняется в силу определения порядка элемента в группе. Кроме того, , 1 ≤ < n -1= O n (a ), откуда в силу определения порядка элемента, выполняется (2).

Пусть теперь выполнены (1) и (2). Покажем, что O n (a )=n -1.

В силу (1), O n (a )\(n -1). В силу (2), O n (a ) не делит . Значит, O n (a )=n -1.

Результатами только что доказанной теоремы можно пользоваться для нахождения порождающего элемента группы U p , причем проверять стоит только второй пункт, так как первый для простого модуля выполняется автоматически согласно теореме Ферма. Кроме того, можно вывести правило : если a 1 , a 2 не являются порождающими элементами группы U p , то a 1 a 2 также не является порождающим элементом U p . Отсюда делаем вывод о том, что наименьший порождающий элемент группы U p – простое число.

Пример

p =71. p -1=70=2·5·7.

Для того чтобы a являлся порождающим элементом, необходимо и достаточно, чтобы выполнялись условия: a 10 1(mod n ), a 14 1(mod n ), a 35 1(mod n ).

Будем испытывать числа из U 71 . Вместо a b mod 71 для краткости будем писать a b .

2: 2 10 =30, 2 14 =54, 2 35 =1. 2 не является порождающим элементом.

3: 3 10 =48, 3 14 =54, 3 35 =1. 3 не является порождающим элементом.

5: 5 10 = 1. 5 не является порождающим элементом.

7: 7 10 =45, 7 14 =54, 7 35 =70. 7 – порождающий элемент.

Итак, наименьший порождающий элемент группы U 71 (или первообразный корень по модулю 71) есть 7.

Существование и количество первообразных корней.

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

Теорема 1

Первообразные корни по модулю m существуют m =2, 4, p α или 2p α , где p – простое нечетное число.

Теорема 2

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

Пример:

Определить количество первообразных корней по модулю 10.

10 = 2·5=2р . Первообразные корни существуют. Найдем их количество.

φ(φ(10))=φ(4)=2.

Проверим результат. U 10 ={1, 3, 7, 9}

3 2 =9, 3 3 =7, 3 4 =1. O 10 (3)=4=φ(10). 3 – первообразный корень.

7 2 =9, 7 3 =3, 7 4 =1. O 10 (7)=4=φ(10). 7 – первообразный корень.

9 2 =1. O 10 (9)=2.

Действительно, нашлись два первообразных корня по модулю 10.

Теорема 3

Пусть с =φ(m ), q 1 , q 2 , … , q k – различные простые делители с . Тогда g : (g ,m )=1 – первообразный корень по модулю m не выполняется ни одно из сравнений , i= 1,2,…,k .

Теорема, доказанная в предыдущем пункте, является частным случаем данной теоремы при простом n .

Дискретные логарифмы.

Если g – первообразный корень по модулю m (порождающий элемент U m ), то, если γ пробегает полную систему вычетов по модулю φ(m ), то g γ пробегает приведенную систему вычетов по модулю m .

Для чисел a : (a ,m )=1 введем понятие об индексе, или о дискретном логарифме.

Если a≡g γ (mod m ), то γ называется индексом , или дискретным логарифмом числа а по основанию g по модулю m .

В теории чисел принято употреблять слово «индекс» и писать γ=ind g a , но в криптографии применяют сочетание «дискретный логарифм» и пишут γ=log g a . Поскольку на протяжении настоящего пособия не раз встретится упоминание о так называемой задаче дискретного логарифмирования, будем употреблять последний вариант названия и написания. Тем более, что дискретные логарифмы обладают некоторыми свойствами логарифмов непрерывных:

Свойство 1: Дискретный логарифм разнозначен в полной системе вычетов по модулю φ(m ).

Свойство 2: log g ab …h≡ log g a +log g b +…+log g h (mod φ(m )).

Свойство 3: log g a n ≡n log g a (mod φ(m )).

Доказательство этих свойств не представляет сложности и является прямым следствием определений дискретного логарифма и первообразного корня.

Решение. Составляем неопределенное уравнение , где и - количества марок 1-го и 2-го типов соответственно..gif" width="91" height="57 src=">.gif" width="15" height="16 src=">.gif" width="11" height="17 src=">.gif" width="11" height="17"> принимает значения . Им соответствуют решения уравнения

,

,

.

Ответ: https://pandia.ru/text/79/541/images/image521.gif" width="113" height="25 src=">.gif" width="53" height="48">. При каких значениях числа дробь будет сократимой?

Решение. Дробь сократима, когда наибольший общий делитель числителя и знаменателя больше 1. Если НОД, то . Исключая из этой системы число , получим ..gif" width="97" height="24 src=">. Решая последнее неопределенное уравнение, получим , ..gif" width="125 height=23" height="23">

Ответ: Дробь может быть сократима только на 11 при

10. Первообразные корни и индексы

Задача №36. Найти первообразный корень по модулю 17.

Решение. Проверим число 2:

Это означает, что показатель числа 2 по модулю 17 равен 8, и число 2 не является первообразным корнем по модулю 17.

Проверим число 3:

Показатель числа 3 по модулю 17 равен 16, поэтому число 3 является первообразным корнем по модулю 17.

Задача №37. На циферблате часов расставить числа 1,2,3,…,12 так, чтобы для любых трех чисел , стоящих подряд, число делилось на 13.

Решение. Число 13 – простое. Возьмем любой первообразный корень по модулю 13, например 2. Выпишем его двенадцать степеней:

2,4,8,16,32,64,128,256,512,1024,2048,4096.

Это геометрическая прогрессия. По свойству геометрической прогрессии квадрат любого члена равен произведению двух соседних членов: DIV_ADBLOCK85">

2,4,8,3,6,12,11,9,5,10,7,1,

то полученная последовательность будет удовлетворять условию задачи. Эти числа можно расставить на циферблате начиная с любого места. Кроме того, можно двигаться как по часовой стрелке, так и против часовой стрелки.

11. Степенные и показательные сравнения

Задача №38. Решить сравнение https://pandia.ru/text/79/541/images/image539.gif" width="17" height="17">. Составим таблицу индексов по модулю 11 и основанию 2.

Проиндексируем данное сравнение и получим новое сравнение по модулю ..gif" width="256" height="24">,

,

,

,

.

По таблице индексов находим .

Ответ: https://pandia.ru/text/79/541/images/image550.gif" width="128" height="28 src=">.

Решение. Проиндексируем данное сравнение, воспользовавшись таблицей индексов из предыдущего примера:

Ответ: https://pandia.ru/text/79/541/images/image553.gif" width="176" height="28">.

Решение. Преобразуем сравнения путем замены коэффициентов на другие, сравнимые с ними по модулю 13:

https://pandia.ru/text/79/541/images/image556.gif" width="220" height="25">.

12. Символ Лежандра

Задача №41. Вычислить символ Лежандра https://pandia.ru/text/79/541/images/image558.gif" width="457" height="116">

Задача №42. Доказать, что произведение двух последовательных натуральных чисел при делении на 17 не может давать в остатке 1.

Решение. Пусть произведение двух последовательных натуральных чисел и https://pandia.ru/text/79/541/images/image560.gif" width="159" height="24">. Преобразуем, пользуясь свойствами сравнений:

Последнее сравнение возможно, если число 5 является квадратичным вычетом по модулю 17. Проверим с помощью символа Лежандра.

Это означает, что число 5 является квадратичным невычетом по модулю 17, поэтому сравнение не имеет решения.

Задача №43. Доказать, что простое число вида https://pandia.ru/text/79/541/images/image565.gif" width="85" height="28">. Тогда . Отсюда получаем . Числа и взаимно просты с . Возьмем число такое, что . Тогда . Это означало бы, что число (-1) является квадратичным вычетом по модулю . Но значение символа Лежандра для числа (-1) равно , т. е. (-1) является квадратичным невычетом по модулю .

Задача №44. Числа и можно представить в виде суммы квадратов двух целых чисел. Доказать, что их произведение также можно представить в виде суммы квадратов двух целых чисел.

Решение. Пусть и . Тогда

Задача №45. Доказать, что число является суммой квадратов двух целых чисел, где https://pandia.ru/text/79/541/images/image576.gif" width="105 height=24" height="24">

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 3

1. Основная теорема арифметики.

2. Системы сравнений 1-ой степени. Китайская теорема об остатках.

3. Найти показатель, которому принадлежит число 9 по модулю 17.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 4

1. Простые числа. Теорема Евклида.

«Нижегородский государственный университет им. ».

Нижний Новгород, пр. Гагарина, 23

В настоящем пункте будем рассматривать число n , причем n -1= * - каноническое разложение на простые сомножители.

Теорема

O n (a )=n -1 1) a n -1 ≡1(mod n );

2) , 1(mod n ).

Доказательство:

Пусть O n (a )=n -1. Тогда (1) выполняется в силу определения порядка элемента в группе. Кроме того, , 1 ≤ < n -1= O n (a ), откуда в силу определения порядка элемента, выполняется (2).

Пусть теперь выполнены (1) и (2). Покажем, что O n (a )=n -1.

В силу (1), O n (a )\(n -1). В силу (2), O n (a ) не делит . Значит, O n (a )=n -1.

Результатами только что доказанной теоремы можно пользоваться для нахождения порождающего элемента группы U p , причем проверять стоит только второй пункт, так как первый для простого модуля выполняется автоматически согласно теореме Ферма. Кроме того, можно вывести правило : если a 1 , a 2 не являются порождающими элементами группы U p , то a 1 a 2 также не является порождающим элементом U p . Отсюда делаем вывод о том, что наименьший порождающий элемент группы U p – простое число.

Пример

p =71. p -1=70=2·5·7.

Для того чтобы a являлся порождающим элементом, необходимо и достаточно, чтобы выполнялись условия: a 10 1(mod n ), a 14 1(mod n ), a 35 1(mod n ).

Будем испытывать числа из U 71 . Вместо a b mod 71 для краткости будем писать a b .

2: 2 10 =30, 2 14 =54, 2 35 =1. 2 не является порождающим элементом.

3: 3 10 =48, 3 14 =54, 3 35 =1. 3 не является порождающим элементом.

Определение 1: Показателем (порядком) целого числа a по данному модулю m называется наименьшее целое положительное число, обозначаемое через , которое удовлетворяет следующему сравнению: .

Пример 1. Найти .

Составим последовательно сравнения вида . Наименьшее значение k, при котором получим b=1 и будет искомой характеристикой.

Следовательно, =5.

Теорема 1: Справедливы следующие утверждения:

3.

Теорема 2: Сравнение имеет место тогда и только тогда, когда .

Определение 2: Класс вычетов называется первообразным корнем по модулю m, если показатель класса вычетов равен функции Эйлера, т.е. . Вместе с классом мы будем называть первообразными корнями и все числа этого класса.

Чтобы убедиться, что а, где (а,m)=1, - первообразный корень по модулю m, достаточно проверить, что , где к – собственные делители .

Пример 2. По модулю 54 класс - первообразный корень. Действительно, . Собственные делители равны k = {1, 2, 3, 6, 9}. Легко проверить, что при всех k.

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

Для нахождения первообразного корня по простому модулю m можно пользоваться следующим критерием:

Лемма: Пусть и - различные простые делители числа с. Для того чтобы число g, (g, m)=1 было первообразным корнем по модулю m, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений

.

Пример 3: Найти первообразный корень по модулю 41.

Решение: Имеем . Следовательно, для того чтобы число g было первообразным корнем по модулю 41, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений:

Испытывая числа 2,3,4,…, находим

Отсюда видим, что число 6 – первообразный корень, так как оно не удовлетворяет ни одному из сравнений (*).

Определение 3. Пусть . Число s называется индексом числа b по модулю m и основанию a, если имеет место сравнение: . При этом используют обозначение .

Пример 4. Так как .

Ввиду практической пользы индексов для каждого простого модуля p (не слишком большого) составлены таблицы индексов (см. например в ). Это две таблицы: одна – для нахождения индекса по числу, другая – для нахождения числа по индексу.

Пример 5. Построить таблицы индексов для модуля p=41.

В примере 3 было показано, что первообразным корнем по модулю 41 является число. Его мы и примем за основание индексов. Находим сравнения (сравнения берутся по модулю 41):

Здесь, номер строки указывает число десятков, номер столбца – число единиц. Так, например, чтобы найти ind 25 воспользуемся таблицей слева. Искомый индекс находится на пересечении 2 строки и 5 столбца и равен 4. Число, индекс которого равен 33 найдем из второй таблицы на пересечении 3 строки и 3 столбца. Это число 17.

Теорема 3. Пусть - первообразный корень по модулю m, (b,m)=1. Тогда сравнение имеет место тогда и только тогда, когда

Теорема 4. Пусть - первообразный корень по модулю m, . Тогда