Математические методы криптографии (ММК) и ЗИ    

ПМ 010302           

Математические методы криптографии (ММК) и ЗИ    

Толстиков А.В.

Практическое занятие 3. Порядки. Первообразные корни. Индексы. Характеры

 

1. Порядок числа и класса вычетов по модулю и их свойства..

2. Первообразные корни их существование и свойства.

3. Индексы и их свойства. Определение дискретного логарифма.

4. Квадратичные сравнения. Квадратичные вычеты. Символ Лежандра и его свойства. Символ Якоби.

5. Числовые характеры.

Литература. Виноградов И.М. – С. 396-442.

Молдовян Н.А., Молдовян А.А.. – С. 79-92.

Задачи для решения на практическом занятии и для самостоятельного решения

1. Найти показатель числа a по модулю m.

1) a= 4, m= 35; 2) a= 41, m= 137; 3) a= 13, m= 315; 4) a= 15, m= 733; 5) a= 7, m= 128.

2. Найти первообразный корень по модулю m.

1) m = 113; 2) m = 98; 3) m = 150; 4) m = 81; 5) m = 169.

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

1) m = 67; 2) m = 47; 3) m = 97; 4) m = 131; 5) m = 653.

4. Определить число чисел относящихся к показателю a по модулю m.

1) a = 2, m = 67; 2) a = 2, m = 47; 3) a = 2, m = 97; 4) a = 2, m = 131;

5) a = 11, m = 67; 6) a = 11, m = 23; 7) a = 11, m = 133.  

5. Указать все показатели по модулю m.

1) m= 137; 2) m= 196; 3) m= 386; 4) m= 625; 5) m= 3×5×129×37; 5) m= 3×7×257.

6. Составить таблицу индексов по mod m. Найти индексы чисел a, b по модулю m. Найти x, y если по mod m ind _g x = c, ind _g y = d.

1) m= 13, a= 4, b = 315, c= 41, d= 28; 2) m= 23, a= 4, b = 315, c= 41, d= 28; 3) m= 43, a= 4, b = 315, c= 41, d= 28.

7. Решить сравнения

1)  2)

3)

8. Извлечь квадратный корень из чисел a, b, c, d по модулю m.

1) m= 97, a= 4, b = 315, c= 41, d= 28; 2) m= 897, a= 537, b = 439, c= 246, d= 238;

3) m = 79, a = 23, b = 26, c = 51, d = 65.

9. Вычислить символ Лежандра .

1) a= 14, b= 41; 2) a= 34, b =47; 3) a= 442, b= 223; 4) a= 42, b= 421; 5) a= 56, b = 599. 

10. Выяснить разрешимо ли сравнение .

1) a= 15, b= 31; 2) a= 14, b =47; 3) a= 42, b= 223; 4) a= 412, b= 421; 5) a= 76, b= 521. 

11. Разрешимо ли сравнение  и в случае его разрешимости найти его число разрешений.

1) a= 7, b= 4×11×41; 2) a= 37, b = 4×11×47; 3) a= 441, b= 16×121×169; 4) a= 19, b= 289× 32×31×471.

12. Построить один неглавный характер по модулю m и найти все его значения на полной системе вычетов 0, 1, …, m -1.

1) m= 14; 2) m= 20; 3) m= 15; 4) m= 18; 5) m= 48.

13. Составить программы.

1. Составить программу вычисления показателя числа по модулю.

2. Составить программы вычисления наименьшего первообразного корня по модулю.

3. Составить программу для вычисления индекса числа.

4. Составить программу для составления таблицы индексов.

5. Составить программу для решения двучленного сравнения по модулю

6. Составить программу вычисления вычетов данной степени по модулю.

7. Составить программу для вычисления символа Лежандра.

8. Составить программу для вычисления символа Якоби.

9. Составить программу, для составления всех характеров по модулю.

10. Составить программу, для вычисления значения характера по модулю.

 

Числовые характеры.

Определение 1. Пусть - каноническое разложение числа m,      Числа c, c ₀, c ₁,…, c_k определяются из условий:

                               (1)

.

Числа R, R ₀, R ₁,…, R_k обозначают какие-нибудь корни уравнений:

                         (2)

т.е. числа вида .

При (a, m) =1 полагаем

,                                     (3)

где g, g₀, g₁,…, g _k  - система индексов числа a, определенная соотношениями:

                                            (4)

 

При (a, m) >1 полагаем

                                                    (5)                                     

Определенную таким образом функцию называем числовым характером по модулю m.

Определение 2. Если все корни R, R ₀, R ₁,…, R_k равны 1, то характер называется главным характером по модулю m. Главный характер имеет значение 1, если (a, m) =1, и значение 0, если (a, m) >1.

Пример 1. Построить один неглавный характер по модулю 30 и найти все его значения на полной системе вычетов 0, 1, …, 29.

Имеем 30 = 2×3×5. Вычисляем числа с, с ₀, с ₁, с ₂ по формулам (1):

с = 1,   с ₀ = 1, с ₁ =2, с ₂ = 4.

Составим систему уравнений (2):

и находим ее решения

.

Найдем первообразные корни g ₁ = 2, g ₂ = 2 соответственно по модулям p ₁ = 3, p ₂ = 5. Рассматриваем системы сравнений (4):

                                                  (6)

и находим по каждому числу a = 0, 1, …, 29, взаимно простому с 30 систему индексов g, g₀, g₁, g₂ . Учитываем, что при (a, m) >1 =0.

Тогда c(0)= c(2)= c(3)= c(4)= c(5)= c(6)= c(8)= c(9)= c(10)= c(12)= c(14)= =c(15)= c(16)= c(18)= c(20)= c(21)= c(22)= c(24)= c(25)= c(26)= c(27)= c(28)=0.

Находим c(1) =1. Далее вычисляем c(a), при a = 7, 11, 13, 17, 19, 23, 29. При этих значениях a системы сравнений (6) принимают вид:

Находим решения соответствующих систем:

(g, g₀, g₁, g₂) = (0, 0, 2, 3), (0, 0, 1, 0), (0, 0, 0, 1), (0, 0, 1, 3), (0, 0, 0, 2), (0, 0, 1, 1),    (0, 0, 1, 2),

Вычисляем соответствующие значения характеров по формуле (3), которая в нашем случае принимает вид:

.

c(7) = - i, c(11) =  -1, c(13) = i, c(17) = i, c(19) = -1, c(23) = - i, c(29) = 1.

Заполняем таблицу значений найденного характера:

a	0	1	2	3	4	5	6	7	8	9
0	0	1	0	0	0	0	0	i	0	0
1	0	-1	0	i	0	0	0	i	0	0
2	0	0	0	-i	0	0	0	0	0	1

 

ПМ 010302           

Математические методы криптографии (ММК) и ЗИ    

Толстиков А.В.

Практическое занятие 3. Порядки. Первообразные корни. Индексы. Характеры

 

1. Порядок числа и класса вычетов по модулю и их свойства..

2. Первообразные корни их существование и свойства.

3. Индексы и их свойства. Определение дискретного логарифма.

4. Квадратичные сравнения. Квадратичные вычеты. Символ Лежандра и его свойства. Символ Якоби.

5. Числовые характеры.

Литература. Виноградов И.М. – С. 396-442.