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

Ответ: 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 = 34743 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 = 14632 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 = 65637 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 = 17420 = 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 = 17408 = 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 = 15372 = 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 = 14238 = 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 = 14170 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 10164 = 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 = 239127 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, = 15625 = 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) Переходим к степенной форме и раскрываем скобки(6x4+3x3+х+)(2х+3)=8x5+5x4+2x2+3x+9x4+6x3+3x++4 = x5+(5+2)x4+6x3+2x2+(3+3)x+4.2) Слагаемые в скобках представляем в полиномиальной форме, выполня-ем сложение по mod 2 и переходим обратно к степенной форме5+2 = а2+а+1+а2 = а+1 = 3; 3+3 = 0;А(х) = x5+3x4+6x3+2x2+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) Переходим к степенной форме и раскрываем скобки(6x4+3x3+х+)(2х+3)=8x5+5x4+2x2+3x+9x4+6x3+3x++4 = x5+(5+2)x4+6x3+2x2+(3+3)x+4.2) Слагаемые в скобках представляем в полиномиальной форме, выполня-ем сложение по mod 2 и переходим обратно к степенной форме5+2 = а2+а+1+а2 = а+1 = 3; 3+3 = 0;А(х) = x5+3x4+6x3+2x2+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) Переходим к степенной форме и раскрываем скобки(6x4+3x3+х+)(2х+3)=8x5+5x4+2x2+3x+9x4+6x3+3x++4 = x5+(5+2)x4+6x3+2x2+(3+3)x+4.2) Слагаемые в скобках представляем в полиномиальной форме, выполня-ем сложение по mod 2 и переходим обратно к степенной форме5+2 = а2+а+1+а2 = а+1 = 3; 3+3 = 0;А(х) = x5+3x4+6x3+2x2+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) = 7x2+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.