Найти все первообразные корни по модулю 17. Вычисление первообразного корня (алгоритм Эль-Гамаля)

Определение 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):

N	0	1	2	3	4	5	6	7	8	9
0		0	26	15	12	22	1	39	38	30
1	8	3	27	31	25	37	24	33	16	9
2	34	14	29	36	13	4	17	5	11	7
3	23	28	10	18	19	21	2	32	35	6
4	20

I	0	1	2	3	4	5	6	7	8	9
0	1	6	36	11	25	27	39	29	10	19
1	32	28	4	24	21	3	18	26	33	34
2	40	35	5	30	16	14	2	12	31	22
3	9	13	37	17	20	38	23	15	8	7

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

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

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

В настоящем пункте будем рассматривать число 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 )).

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

В настоящем пункте будем рассматривать число 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-го и 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

Вычисление первообразного корня (алгоритм Эль-Гамаля)

Общие положения

В основе алгоритма Эль-Гамаля лежит процедура открытого распределения ключей, опубликована в 1976 году в работе У. Диффи и М.Э. Хеллмана «Новые направления в криптографии».

Ключи шифрования и дешифрования вычисляются по алгоритму, где P - большое простое число, g - первообразный корень по модулю P. Секретное число a может быть любым целым числом, лучше случайным. Величина числа не ограничена.

Первообразным (примитивным) корнем по модулю P, будет число g < P и взаимно простое с P, принадлежащее показателю d. Показатель d (дискретный логарифм числа g по модулю P при основынии i т.е или) является наименьшим, натуральным числом, обеспечивающим сравнение. Отсюда следует, что для взаимно простых P и = P-1 чисел показатель (индекс) и следовательно, где: i = 2,3,4,…,P-2. Исходя из того факта, что первым основанием i, (для простого P и взаимно простого) образующим первый примитивный корень могут быть только числа 2 и 3, следовательно, вычислить первый корень не составляет труда. Например, для модуля P=11, первым корнем будет число 2, так как: = , где: и d = 5 = . Для модуля P = 7 первым корнем будет число 3^3(mod 7) = 6, а вторым корнем будет, 5^3(mod 7) = 6.

Первообразные корни образуют мультипликативную группу кольца, которая представляет ряд чисел, степени которых g 0 , g 1 , g 2 ,…g ц(m)-1 представляет собой совокупность всех взаимно простых с m чисел, меньших m. То есть g k пробегает систему вычетов при k = 1, 2,… ц(m), где: ц(m) - функция Эйлера.

В программе использовала компоненты SpinEdit 1,2,3- для ввода чисел, Memo 1,2 - для отображения результатов и командные кнопки Button 1,2. (рис. 9)

Примечание: Для вычисления значенией действительных чисел в раздел Uses Unit"aвключить модуль Math.

Реализация алгоритмов

function Simple(n:integer):Boolean;

var k:Boolean; i:integer;

if n<>2 then

for i:=2 to trunc(sqrt(n))+1 do

if n mod i = 0 then

function IntModPower(A,B,P:integer):integer;

x:array of integer;

for i:=2 to B do

x[i]:=x * A mod P;

procedure TForm1.Button1Click(Sender: TObject);

for i:= SpinEdit1.Value to SpinEdit2.Value do

if Simple(i) = true then Memo1.Lines.Add(IntToStr(i));

procedure TForm1.Button3Click(Sender: TObject);

P:= SpinEdit3.Value;

d:= (P-1) div 2;

for i:= 2 to P-2 do

if (IntModPower(i,d,P) = P-1) then

Memo2.Lines.Add("g = " + IntToStr(i) + " (^" + IntToStr(d) + ") = " + FloatToStr(Power(i,d)));