Криптография в теории чисел

Ответ: x = 2. б) 32x 102 mod 123. Решим сравнение с помощью алгоритма Эвклида.

1. Определяем (a, m): (32,123) = 1. Сравнение имеет одно решение.

2. Выполняем алгоритм Евклида для 123/32: — неполные частные q1 = 3, q2 = 1, q3 = 5, q4 = 2, q5 = 2, n = 5;- P1 = q1 = 3, P2 = 13+1 = 4, P3 = 54+3 = 23, P4 = 223+4 = 50.

3. Решение сравненияx (-1)4P4b mod m 50102 mod 123 57 mod 123.

4. Проверка: 3257 = 1824 102 mod 123.

5. Ответ: x = 57. в) 111x 75 mod 321.

1. Так как (111,321) = d = 3, то сравнение имеет три решения (с учетом то-го, что 75 делится на 3).

2. Делим на d = 3, получаем сравнение37x 25 mod 107.

3. Выполняем алгоритм Евклида для 107/37:НайдемPi = qiPi-1+Pi-2 дляP-1 = 0, P0 = 1. Все результаты сведем в таблицу Из таблицы: n = 4, Pn-1 = 26.

4. Определяем первое решениеx1 (-1)32625 mod 107 -2625 99 mod 107.

5. Остальные решения: x2 = 99+107 = 206, x3 = 206+107 = 313.

6. Проверка для х3 = 313:

111 313 = 34 743 75 mod 321. Ответ: x1 = 99, x2 = 206, x3 = 313.

г) 81x 34 mod 95.

1. Так как (81,95) = d = 1, то сравнение имеет одно решение.

2. Выполняем алгоритм Евклида для 95/81.Результаты деления по алгоритму Евклида и Pi = qiPi-1+Pi-2 для начальныхусловий P-1 = 0, P0 = 1 сведем в таблицу3. Определяем решениеx (-1)53434 mod 95 79 mod 95.

4. Проверка для х = 798179 = 6399 34 mod 95. Ответ: x = 79. д) 124x 88 mod 144.

1. (a, m) = 4, b = 88 делится на 4. Значит, сравнение имеет четыре решения.

2. Делим все части сравнения на d=4:31x = 22 mod 36;3. Неполные частные от деления по алгоритму Евклида для 36/31 иPi = qiPi-1+Pi-2 для начальных условий P-1 = 0, P0 = 1 сведены в таблицу.

Из таблицы: n = 3, P2 = 7.

4. Первое решение: x1 = (-1)2722 mod 36 = 154 mod 36 = 10 mod 36;5. Другие решения: x2 = x1+36 = 46;x3 = x2+36 = 82;x4 = x3+36 = 118.

6. Проверка для x4 = 118:

124118 = 14 632 88 mod 144. Ответ: x1 = 10, x2 = 46, x3 = 82, x4 = 118.

е) 351x 99 mod 198.

1. Так как (351,198) = d = 9, то сравнение имеет девять решений (с учетомтого, что 99 делится на 9).

2. Делим все части сравнения на d = 9, получаем сравнение:

39x 11 mod 22.

3. Выполняем алгоритм Евклида для 22/39:Результаты деления по алгоритму Евклида и Pi = qiPi-1+Pi-2 для начальныхусловий P-1 = 0, P0 = 1 сведем в таблицу.

Из таблицы: Pn-1 = 9, n = 6.

4. Определяем первое решениеx1 )911 mod 22 -99 mod 22 11 mod 22.

5. Остальные решения: x2 = 11+22 = 33, x3 = 33+22 = 55, x4 = 55+22 = 77, x5 = 77+22 = 99, x6 = 99+22 = 121, x7 = 121+22 = 143, x8 = 143+22 = 165, x9 = 165+22 = 187.

6. Проверка для x9 = 187:

351187 = 65 637 99 mod 198. Ответ: x1 = 11, x2 = 33, x3 = 55, x4 = 77, x5 = 99, x6 = 121, x7 = 143, x8 = 165,= 187. Решение к задаче 1.

18.а) 134x 92 mod 152.

1. (a, m) = 2, b = 92 делится на 2. Значит, сравнение имеет два решения.

2. Разделим все части сравнения на d = 2:67x = 46 mod 76.

3. Результаты деления по алгоритму Евклида для 76/67 и Pi = qiPi-1+Pi-2 дляначальных условий = 0, P0 = 1 сведены в таблицу.

Из таблицы: n = 4, P3 = 17.

4. Первое решение: x1 = (-1)31746 mod 76 = -782 mod 76 = 54 mod 76;5. Второе решениеx2 = x1+76 = 130.

6. Проверка для x2 = 130: 134130 = 17 420 = 92 mod 152. Ответ: x1 = 54; x2 = 130.

б) 128x 34 mod 146.

1. Так как (128,146) = d = 2, то сравнение имеет два решения (с учетом то-го, что 34 делится на 2).

2. Делим все части сравнения на d = 2, получаем сравнение:

64x 17 mod 73.

3. Выполняем алгоритм Евклида для 73/64:Результаты деления по алгоритму Евклида и Pi = qiPi-1+Pi-2 для начальныхусловий P-1 = 0, P0 = 1 сведены в таблицу.

Из таблицы: n = 3, Pn-1 = 8.

4. Определяем первое решениеx1 (-1)2817 mod 73 63 mod 73 .

5. Остальные решения: x2 = 63+73 = 136.

6. Проверка для x2 = 136: 128136 = 17 408 = 34 mod 146. Ответ: x1 = 63; x2 = 136.

в) 122x 96 mod 134.

1. Так как (122,134) = d = 2, то сравнение имеет два решения (с учетом то-го, что 96 делится на 2).

2. Делим все части сравнения на d = 2, получаем сравнение:

61x = 48 mod 67.

3. Результаты деления по алгоритму Евклида для 67/61 и Pi = qiPi-1+Pi-2 дляначальных условий P-1 = 0, P0 = 1 сведены в таблицу.

Из таблицы: n = 3, Pn-1 = 11.

4. Первое решениеx1 = (-1)21148 mod 67 = 528 mod 67 = 59 mod 67.

5. Второе решениеx2 = x1+67 = 126;6. Проверка для x2 = 126: 122126 = 15 372 = 96 mod 134. Ответ: x1 = 59; x2 = 126.

г) 126x 38 mod 142.

1. Так как (126,142) = d = 2, то сравнение имеет два решения (с учетом то-го, что 38 делится на 2).

2. Делим все части сравнения на d = 2, получаем сравнение:

63x = 19 mod 71;3. Определяем qi по алгоритму Евклида для 71/63 и Pi = qiPi-1+Pi-2 дляначальных условий P-1 = 0, P0 = 14. Первое решение: x1 = 919 mod 71 = -171 mod 71 = 42 mod 71.

5. Второе решение: x2 = x1+71 = 113.

6. Проверка для x2 = 113: 126113 = 14 238 = 38 mod 142. Ответ: x1 = 42; x2 = 113.

д) 130x 58 mod 144.

1. Так как (144,130) = d = 2, то сравнение имеет два решения (с учетом то-го, что 58 делится на 2).

2. Делим все части сравнения на d = 2, получаем сравнение:

65x = 29 mod 72;3. Определяем qi по алгоритму Евклида для 72/65 и Pi = qiPi-1+Pi-2 дляначальных условий P-1 = 0, P0 = 1Из таблицы: n = 4, Pn-1 = P3 = 31.

4. Определяем первое решение сравнения: x1 = 3129 -899 mod 72 37 mod 72.

5. Второе решение: x2 = x1+72 = 37+72 = 109.

6. Проверка х2 = 109: 130109 = 14 170 58 mod 144. Ответ: х1 = 37, x2=109.

е) 132x 82 mod 142.

1. Так как (142,132) = d = 2, то сравнение имеет два решения (с учетом то-го, что 82 делится на 2).

2. Делим все части сравнения на d = 2, получаем сравнение:

66x = 41 mod 71.

3. Определяем qi по алгоритму Евклида для 71/66 и Pi = qiPi-1+Pi-2 дляначальных условий P-1 = 0, P0 = 1Из таблицы: n = 3, Pn-1 = P2 = 14.

4. Определяем первое решение сравнения: x1 = 1441 574 mod 71 6 mod 71.

5. Второе решение: x2 = x1+71 = 6+71 = 77.

6. Проверка х2 = 77: 13277 10 164 = 82 mod 142. Ответ: х1 = 6, x2=77.ж) 152х 29 mod 211.

1. Так как (152,211) = d = 1, то сравнение имеет одно решение.

2. Определяем qi по алгоритму Евклида для 211/152 и Pi = qiPi-1+Pi-2 дляначальных условий = 0, P0 = 1Из таблицы: n = 8, Pn-1 = P7 = 93.

3. Определяем решение сравненияx = Pn-1b mod m = -9329 -165 mod 211 46 mod 211.

4. Проверка х = 46: 15246 = 6992 29 mod 211. Ответ: х = 46. з) 579х 273 mod 462.

1. Так как α= 579 > m = 462, то определим 579 117 mod 462, получаемэквивалентное уравнение 117x 273 mod 462.

2. α= 117 = 3313, т = 462 = 23711, b = 273 = 3713. (a, m) = 3. Следова-тельно, сравнение имеет три решения.

3. Делим все части сравнения на d = 3, получаем сравнение:

39x 91 mod 154.

4. Выполняем алгоритм Евклида для 154/39, и Pi = qiPi-1+Pi-2 для началь-ных условий P-1 = 0, P0 = 1Из таблицы: n = 4, P3 = 755. Определяем первое решение х1: x1 = 7591 mod 154 = -6825 mod 154 -49 mod 154 105 mod 154.

6. Остальные решениях2 = 105+154 = 259, х3 = 259+154 = 413.

7. Проверка для х3 = 413: 579413 = 239 127 273 mod 462. Ответ: х1 = 105, х2 = 259, х3 = 413. Решение к задаче 1.

19.а) a1 = 1; б) a2 = 2; в) a3 = 3; г) a4 = 4.1) Проведем последовательное возведение в степень элементов ai (i=)и определим их показатели (периоды):

а) 1 mod 5, т. е. 1 = 1;б) = 4, = 8 3 mod 5, = 16 1 mod 5, т. е. 2 = 4;в) = 9 4 mod 5, = 27 2 mod 5, = 81 1 mod 5, т. е. 3 = 4;г) = 16 1 mod 5, т. е. 4 = 2.2) При дальнейшем возведении элементов ai в последовательные степенинаблюдается их периодическая повторяемость по модулю 5; для a3 = 3: 35 3mod 5 31, 36 32 mod 5, 37 33 mod 5, 38 34 mod 5 1 mod 5 и т. д.Ответ:1 = 1, 2 = 4, 3 = 4, 4 = 2. Решение к задаче 1.

20.a1 = 1, a2 = 2,…, a6 = 6.

1.Проведем последовательное возведение в степень элементов иопределим их показатели (периоды):

а) 1 mod 7, т. е. 1 = 1;б) = 4, = 8 1 mod 7, т. е. 2 = 3;в) = 9 2 mod 7, = 27 = 6 mod 7, = 81 4 mod 7, = 243 5 mod 7,= 729 1 mod 7, т. е. 3 = 6;г) = 16 2 mod 7, = 64 = 1 mod 7, т. е. 4 = 3;д)= 25 = 3 mod 7, = 125 = 6 mod 7, = 625 = 2 mod 7, = 3125 == 3 mod 7, = 15 625 = 1 mod 7, т. е. 5 = 6;е) = 36 = 1 mod 7, т. е. 6 = 2. Ответ:1 = 1, 2 = 3, 3 = 6, 4 = 3, 5 = 6, 6 = 2. Решение к задаче 1.

21.1. Определяем элементы приведенной системы вычетов по модулю 9:= {1, 2, 4, 5, 7, 8}, (m) = (9) = 6.

2. Вычисляем распределение показателей по элементам (это есть делителичисла 6: 1, 2, 3, 6):1 mod 9, 1 = 1;= 4, 23 = 8, 24 7 mod 9, 25 5 mod 9, 26 1 mod 9, 2 = 6;= 16 7 mod 9, 43 1 mod 9, 4 = 3,= 25 7 mod 9, 53 8 mod 9, 54 4 mod 9, 55 2 mod 9,1 mod 9, 5 = 6;4 mod 9, 73 1 mod 9, 7 = 3,= 64 1 mod 9, 8 = 2. Ответ: 1 = 1,2 = 6,4 = 3,5 = 6,7 = 3,8 = 2. Решение к задаче 1.

22.1. Определяем элементы приведенной системы вычетов по модулю 10:= {1, 3, 7, 9}, (m) = (10)=4.

2. Вычисляем распределение показателей по элементам (это есть делителичисла 4: 1, 2, 4):1 mod 10, 1 = 1;7 mod 10, 34 1 mod 10, 3 = 4;9 mod 10, 73 3 mod 10, 74 1 mod 10, 7 = 4;1 mod 10, 9 = 2;Ответ: 1 = 1,3 = 4,7 = 4,9 = 2. Решение к задаче 1.

23.а) m=9.a1=4; = 7 mod 9, 43 = 1 mod 9;1 = 3. a2=2; = 7 mod 9, 25 = 5 mod 9, 26 = 1 mod 9;2 = 6. Ответ: 1 = 3, 2 = 6. б) m=7.a1=2; = 4 mod 7, 23 = 1 mod 7,1 = 3. a2=3; = 2 mod 7, 33 = 6 mod 7, 34 = 4 mod 7, 35 = 5 mod 7, 36 = 1 mod7;2 = 6. Ответ: 1 = 3, 2 = 6. Решение к задаче 1.

24.а) m=3; (m) = (3) = 2; =2.Ответ:=2.б) m=4;(m) = (4) = 2; =3.Ответ:=3.Решение к задаче 2.

1.Сумма обратных по сложению элементов равна нейтральному элементу, т. е. 0 mod 7. Для элемента 2: 2+x=0 x= 5. Для элемента 3: 3+x=0 x= 4. Для элемента 5: 5+x=0 x= 2. Ответ: обратные по сложению элементы для 2 — 5, для 3 — 4, для 5 — 2. Решение к задаче 2.

2.Произведение обратных по умножению элементов равно нейтральномуэлементу, т. е. 1 mod 7. Для элемента 2: 2x = 1 mod 7 x= 4. Для элемента 3: 3x = 1 mod 7 x= 5. Для элемента 5: 5x = 1 mod 7 x= 3. Для элемента 6: 6x = 1 mod 7 x= 6. Ответ: обратные по умножению элементы для 2 — 4, для 3 — 5, для 5 — 3, для 6 — 6. Решение к задаче 2.

3.а) S = [(3−1 mod 7)+(5−1 mod 11)+(3−1 mod 5)+(4−1 mod 13)] mod 7 == (5+9+2+10) mod 7 = 5;б) S = [(2−1 mod 7)+(7−1 mod 11)+(4−1 mod 5)+(5−1 mod 13)] mod 7 == (4+8+4+8) mod 7 = 3;в) S = [(4−1 mod 7)+(6−1 mod 11)+(4−1 mod 5)+(5−1 mod 13)] mod 7 == (2+2+4+8) mod 7 = 2;г) S = [(5−1 mod 7)+(8−1 mod 11)+(2−1 mod 3)+(3−1 mod 13)] mod 7 == (3+7+2+9) mod 7 = 0. Решение к задаче2.

4.а) GF (2) с элементами 0, 1 т = р = 2б) GF (3) с элементами 0, 1, 2 т = р = 3Решение к задаче 2.

5.Решение к задаче 2.

6.а) GF (5):б) GF (7):в) GF (6):Решение к задаче 2.

7.Решение к задаче 2.

8.Решение к задаче 2.

9.Решение к задаче 2.

10.1) Число элементов поля (порядок поля) равно L = pn= 22=4.2) Полагая п = 2 и придавая коэффициентам ai независимо значения эле-ментов поля GF (2) (т.е. числа 0 и 1), получаем GF (22) = {0, 1, x, x+1}.Элементами расширенного поля GF (22) являются полиномы степени невыше п-1 с коэффициентами из GF (2).3) При построении таблицы сложения учитывается, что операция выпол-няется по mod 2.4) При составлении таблицы умножения элементов поля GF (22) требуетсяконкретизация неприводимого полинома f (x), так как умножение элементовосуществляется по двойному модулю (f (x), p). Для расширенного поля GF (22)существует единственный неприводимый над GF (2) полином степени 2 -f (x) =x2+x+1 (неприводимость f (x) легко проверить, попытавшись разделить егона полиномы х и х+1 без остатка).Определим, к примеру, произведение элементов х+1 и х+1. Выполняяумножение, получаем (х+1)(х+1) = х2+1(mod 2).Разделив полином +1 на полином х2+х+1, находим.

Следовательно, (х+1)(х+1) х modd (+x+1, 2).Аналогичным образом определяются произведения всех возможных парэлементов поля GF ().Решение к задаче 2.

11.1) Элементы множества F образуют полную систему полиномов — вычетовпо двойному модулю (f (x), p = 2):F = {0, 1, x, x+1, x2, x2+1, x2+x+1, x2+x}.2) Построим таблицы сложения и умножения. Для примера определим произведение элементов (х2+х) и (х2+х+1). Выпол-няя умножение, получим (+х)(+х+1) = (х4+х3+х3+х2+х2+х) mod 2 = х4+х.Найдем остаток от деления полинома (х4+х) на f (x) = х3+х2+х+1:Следовательно, (х2+х)(х2+х+1) = х+1 modd (х3+х2+х+1, 2). Аналогичным об-разом вычисляются остальные произведения.

3) Множество F не является полем, так как для элементов х+1, х2+1 и х2+хне существует мультипликативно обратных элементов, что определяется отсут-ствием единичного элемента в 4, 5 и 6 строках таблицы умножения. Решение к задаче 2.

12.1) Элементы расширенного поля GF (32) образуют полную систему поли-номов — вычетов по двойному модулю (f (x), p = 3):GF (32) = {0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2}.2) Построим таблицы сложения и умножения. Для примера определим произведение элементов (2х+2) и (2х+1). Выпол-няя умножение, получим (2х+2)(2х+1) = (4×2+2х+4х+2) mod 3= х2+2.Найдем остаток от деления полинома (х2+2) на f (x) = x2+2x+2, при этом всевычисления будем производить по модулю 3: Следовательно, (2х+2)(2х+1) = х modd (x2+2x+2, 3). Аналогичным образомвычисляются остальные произведения. Решение к задаче 2.

13.1) Проведем последовательное возведение в степень элемента = a с уче-том того, что операции выполняются по двойному модулю (f (a), 2):0 = 1;1 = а;2 = ;3 = а3 mod f (a) = a + 1;4 = а2 +a;5 = (а3 + a2) mod f (a) = a2+ a + 1;6 = (а3 + a2 + a) mod f (a) = (a + 1 + a2+ a) mod 2 = a2+ 1;7 = (а3 + a) mod f (a) = (a + 1 + a) mod 2 = 1. Для обозначения нулевого элемента поля используется формальная запись-= 0.2) Очевидно, что период элемента, а равен (а)=7, т. е. равен max=-1 — по-рядку мультипликативной группы поля. Свойство цикличности группы прояв-ляется в том, что 7 = 0 = 1, 8 = 1, 9 = 2 и т. д.Решение к задаче 2.

14.Для обозначения нулевого элемента поля используется формальная запись-= 0.Проведем последовательное возведение в степень элемента = a с учетомтого, что операции выполняются по двойному модулю (f (a), 3):Полиномиальное представление элементов поля вычисляется последова-тельным возведением примитивного элемента = a в степени с учетом того, что операции выполняются по двойному модулю (f (a), 3).Решение к задаче 2.

15.1) Проведем последовательное возведение в степень элемента = a с уче-том того, что операции выполняются по двойному модулю (f (a), 2):0 = 1;1 = а;2 = а2;3 = a2 + 1;4 = а2 +a+1;5 = a+ 1;6 = a2 + a. Для обозначения нулевого элемента поля используется формальная запись-= 0.2) Очевидно, что период элемента, а равен (а)=7, т. е. равен max=23−1 — по-рядку мультипликативной группы поля. Свойство цикличности группы прояв-ляется в том, что 7 = 0 = 1, 8 = 1, 9 = 2 и т. д.Решение к задаче 2.

16.1) Переходим к степенной форме и раскрываем скобки (6×4+3×3+х+)(2х+3)=8×5+5×4+2×2+3x+9×4+6×3+3x++4 = x5+(5+2)x4+6×3+2×2+(3+3)x+4.2) Слагаемые в скобках представляем в полиномиальной форме, выполня-ем сложение по mod 2 и переходим обратно к степенной форме5+2 = а2+а+1+а2 = а+1 = 3; 3+3 = 0;А (х) = x5+3×4+6×3+2×2+4.3) Вычисляем остаток от деления A (x) на f (x)4) Находим значение полинома R (x), и соответственно А (х), в точкех = 5 = 4.R () = 6(4)2+24+1 = 14+6+1 = 1+6+1 = 6=7 .Ответ: А (5) = 7. Решение к задаче 2.

17.1) Переходим к степенной форме и раскрываем скобки (6×4+3×3+х+)(2х+3)=8×5+5×4+2×2+3x+9×4+6×3+3x++4 = x5+(5+2)x4+6×3+2×2+(3+3)x+4.2) Слагаемые в скобках представляем в полиномиальной форме, выполня-ем сложение по mod 2 и переходим обратно к степенной форме5+2 = а2+а+1+а2 = а+1 = 3; 3+3 = 0;А (х) = x5+3×4+6×3+2×2+4.3) Вычисляем A (x) modd (f (x), 2), т. е. находим остаток от деления A (x) наf (x)4) Находим значение полинома R (x), и соответственно А (х), в точкех = 5 = 4.R (4) = 6(4)2+24+1 = 14+6+1 = 1+6+1 = 6 =7 .Ответ: А (5) = 7. Решение к задаче 2.

18.1) Переходим к степенной форме и раскрываем скобки (6×4+3×3+х+)(2х+3)=8×5+5×4+2×2+3x+9×4+6×3+3x++4 = x5+(5+2)x4+6×3+2×2+(3+3)x+4.2) Слагаемые в скобках представляем в полиномиальной форме, выполня-ем сложение по mod 2 и переходим обратно к степенной форме5+2 = а2+а+1+а2 = а+1 = 3; 3+3 = 0;А (х) = x5+3×4+6×3+2×2+4.3) Вычисляем A (x) mod f (x), т. е. находим остаток от деления A (x) на f (x)4) Находим значение полинома R (x), и соответственно А (х), в точкех = 5 = R (4) = 6(4)2+24+1 = 14+6+1 = 1+6+1 = 6 =7 .5) Ответ: А (5) = 7. Решение к задаче 2.

19.Решение к задаче 2.

20.1)2) Определить число k различных р-сопряженных элементов для элементов4: 4 812; 6:6 1293.3) Определить минимальные полиномы для элементов2 4 81Решение к задаче 2.

21.1)2) Определить число k различных р-сопряженных элементов для элементов4: 4 812; 6: 6 1293.3) Определить минимальные полиномы для элементов.

Решение к задаче 2.

22.а) (x)= x2+x+2; i=3; j=5;б) (x)= x2+2x+2; i=3; j=5;в) (x)= x2+x+2; i=5; j=7;г) (x)= x2+2x+2; i=5; j=7;д) (x)= x2+x+2; i=7; j=3;е) (x)= x2+2x+2; i=7; j=3.Построить расширенное поле GF (), определить функцию следа, мини-мальный полином, аддитивный и мультипликативный характеры для заданногоэлемента поля.

а), в), д)1) Построение поля.

2) Функция следа, минимальный полином, аддитивный и четырехзначныймультипликативный характеры (M = 4, = 1) для элемента 5 (вариант а).Функция следаминимальныйполиномаддитивныйхарактерe (a) = exp (j2trn1a/p);e (5) = exp (j2tr215/3) = exp (j2/3);мультипликативный М-значный характер(a) = exp (j2loga/M);(5) = exp (j2log5/M) = exp (j5/2) = exp (j/2) = +j.Результаты вычислений для вариантов в) и д) сведены в таблицу.

б), г), е)1) Построение поля.

2) Функция следа, минимальный полином, аддитивный и четырехзначныймультипликативный характеры (M = 4, = 1).Решение к задаче 2.

23.1. Значение полинома А (х) в точке х = 5 можно было находить непосред-ственно после пункта 2 без выполнения операции сравнения по модулю f (x); ре-зультат должен быть тот же самый. Покажем это: А (4) = (4)5+3(4)4+6(4)3+2(4)2+4 = 21+19+18+10+4 == 1+а2+а+1+а+1 = а2+1 = 6 = 7.2. При выполнении операции деления полинома на полином и сложении (вычитании) коэффициентов при одинаковых степенях х также осуществляетсяпереход к полиномиальной форме.

3. Упрощенное выражение имеет видA (x) = R (x) = 7×2+3x+1Решение к задаче 2.

24. Решение к задаче 2.

25. Решение к задаче 2.

26.1) N1 = 1;2) N3: 3 = 13; N3 = 30(3−1) = 2;3) N7: 7 = 17; N7 = 70(7−1) = 6;4) N9: 9 = 132; N9 = 31(3−1) = 6;5) N21: 21 = 137; N21 = 30(3−1)70(7−1) = 12;6) N63: 63 = 1327; N63 = 31(3−1)70(7−1) = 36. Решение к задаче 2.

27.Решение к задаче 2.

28.1) Построение поля с примитивным элементом = a:-= 0,0 = 1,1 = a,2 = a+1.2) Проверка выполнения теоремы Ферма. Пусть x = 2, тогда (2)4-2 = 8mod 3-2 = 0. Решение к задаче 2.

29.1. Порядок мультипликативной группы L = -1 = 15 = = 135; следова-тельно существует один элемент с периодом = 1, два элемента с периодом= 3, четыре элемента с периодом = 5 и восемь элементов с периодомmax = 15.2. Подгруппа Н1 порядка L = 1 — это есть тривиальная подгруппа Н1 = {1}.

553. Подгруппа Н2 порядка L = 3 — состоит из двух элементов с периодом= 3 и нейтрального элемента по умножению e = 1, т. е. H2 = {1, 5, 10}.

4. Подгруппа Н3 порядка L = 5 — состоит из элементов с периодом = 5 инейтрального элемента по умножению H3 = {1, 3, 6, 9, 12}.

5. Оставшиеся восемь элементов (, 2, 4, 8, 7, 11, 13, 14) являютсяпримитивными и входят только в основную группу G.Решение к задаче 2.

30.1. В качестве образующего элемента ai смежного класса можно выбратьпроизвольный элемент группы G. Возможны два варианта:

а) ai H: в этом случае смежные классы совпадают с подгруппой Н, например, если a1 = 9, то a1H = {9,39,69,99, 129} = {9,12,1,3,6} = H;б) ai H: в этом случае смежные классы не совпадают с подгруппой Н, например, если a2 = 2 H, то a2H = {2,23, 26,29,129} = {2,5,8,11,14}.

2. Так как группа G имеет порядок L = 15, то она может быть представленакак объединение трех непересекающихся смежных классов. В качестве первоговыступает а1Н, совпадающий с подгруппой Н, в качестве второго — а2Н. Образующим элементом третьего смежного класса целесообразно выби-рать элемент, не входящий в первые два класса. Например, если а3 = , тоa3H = {,4,7,10,13}. В результате имеемG = {a1H} + {a2H} + {a3H}, где символ сложения следует рассматривать как символ объединения. Решение к задаче 2.

31.1. Разложим степень расширения п = 18 простого поля GF (2) на множителип = 18 = 223.

2. Определим различные подполя: GF (2), GF (22), GF (23), GF (26), GF (29).Таким образом, поле GF (218) содержит 5 подполей. Решение к задаче 2.

32.1. Разложим степень расширения п = 18 простого поля GF (2) на множите-ли: п = 18 =233.

2. Определим различные подполя: GF (2), GF (), GF (23), GF (26), GF (29).Таким образом, поле GF () содержит 5 подполей. Решение к задаче 2.

33.Решение к задаче 2.

34.1. ПостроениеполяGF ():= 0, 0 = 1, 1 = a, 2 = a2, 3 = a+1, 4 = a2+a, 5 = a2+a+1, 6 = a2+1.

2. Определениер-сопряженныхэлементов:

а) , 2, 4; k= 3;б) 3, 6, 5; k= 3;в) -= 0; k= 1;г) 0 = 1; k= 1.3. Вычислениеминимальныхполиномов:

Решение к задаче 2.

35.Очевидно, что x9-x = x (x+2)(x2+x+2)(x2+1) (x+1)(x2+2x+2).Все минимальные полиномы являются неприводимыми над полем GF (3).Минимальные полиномы еще и примитивные, так как периодих корней равен max = 32−1 = 8 — порядку мультипликативной группы поляGF (32). Неприводимый полином степени k = 2 не является примитивным, так как период его корней равен () = 4. Решение к задаче 2.

36.