Задания

1. Выяснить, обладают ли свойствами ассоциативности и коммутативности операции *на множестве А, если

A=N, x*y=x+2y; A=N, x*y = x^y;

A=N, x*y=3xy; A=N, x*y =НОД(x,y);

A=Z, x*y=x – y; A=Z, x*y = x²+ y²;

A=R, x*y = sinxcosy; A=R, x*y = x^çyç.

2. Какие из указанных числовых множеств являются группами относительно заданных операций:

1) множество степеней данного вещественного числа с целыми показателями относительно умножения;

2) множество комплексных чисел с фиксированным модулем относитель­но операции умножения;

3) множество положительных действительных чисел относительно операции умножения;

4) отрезок [0,1] относительно операции умножения;

5) отрезок [0,1] относительно операции a*b = {a+b};

6) корни всех степеней из единицы относительно умножения?

3. Какие из указанных множеств квадратных матриц фиксированного поряд­ка образуют группу относительно операции умножения:

1) множество симметрических матриц с вещественными элементами;

2) множество невырожденных матриц с вещественными элементами;

3) множество целочисленных матриц с определителем, равным ±1;

4) множество верхних треугольных матриц с вещественными элементами;

5) множество ортогональных матриц;

6) множество диагональных матриц?

4. Доказать, что множество функций вида у =(ах + b)(сх + d)^-1, где a,b, с, d ÎR, ad–bc¹0, является группой относительно операции композиции функций.

5. Доказать, что если в группе G выполнено условие х² = е, х Î G, то группа G коммутативна.

1. Доказать, что в любой группе (ab)^-1 =b^-1а^-1 и вообще

(a₁a₂…a_n) ^-1 =a_n^-1a_n-1^-1…a₁^-1.

7. Доказать, что множество всех квадратных матриц данного порядка, в каждой строке и каждом столбце которых один элемент равен 1, а остальные 0, образует группу.

8. Составить таблицу Кэли для циклической группы пятого порядка.

9. Найти с точностью до изоморфизма вес группы порядков 3,4, 6. Составить их таблицы Кэли.

10. Доказать, что в конечной группе любое подмножество Н, замкнутое по умножению (h₁,h₂ÎHÞ h₁h₂ÎH ), будет подгруппой.

11. Доказать, что для нетривиального смежного класса gH(eÏgH) выполняется условие h₁,h₂ÎgHÞ h₁h₂ÏH.

12. Доказать, что пересечение двух подгрупп будет подгруппой.

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

14. Найти все подгруппы групп S₆,Z₆,Z₂₄.

15. Разложить:

1) аддитивную группу вещественных чисел по подгруппе целых чисел;

2) аддитивную группу комплексных чисел по подгруппе целых гауссовских чисел;

3) симметрическую группу S_n по подгруппе подстановок, оставляющей элемент 1 на месте;

4) группу Z₆ по своим подгруппам;

5) группу S₃ по своим подгруппам.

16. Пусть a ÎG. Доказать, что множество элементов {х | ха = ах, хÎG}, называемое централизатором элемента а, является подгруппой.

17. Доказать, что множество элементов {х | ха = ах, "хÏG}, называемое централизатором группы, является нормальной подгруппой.

18. Найти централизаторы элементов

в группе GL(2,R).

19. Найти центр группы GL(2,R).

20. Показать, что порядки элементов а и а^-1 равны.

21. Показать, что порядки элементов аb и bа равны.

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

23. Пусть А и В нормальны в G, AÇB=e, тогда каждый элемент aÎA перестановочен с каждым элементом bÎB.

24. Подгруппа, порожденная элементами вида аbа^-1b^-1 (коммутаторами), называется коммутантом. Доказать, что

1) аbа^-1b^-1= е Û аb=bа;

2) К < G;

3) фактор-группа G/K – абелева;

4) если G/ Н – абелева, то К Ì Н.

25. Определить с точностью до изоморфизма все абелевы группы порядка 8.

26. Пусть Н – подмножество группы G c условием h₁,h₂ÎHÞ h₁h₂ÏH. Доказать, что |Н| £ 0.5|G|.

27. Вычислить следующие произведения подстановок:

1) (1,2) (1,3) (1,4) (2,3) (3,5);

2) (125) (124) (129);

3) f¹⁰⁰ , где

28. Найти подстановку Х, если АХВ² =С,

29. Доказать, что две подстановки сопряжены тогда и только тогда, когда имеют одинаковое количество циклов каждой длины.

30. Доказать, что в булевом кольце (х² = х):

1) умножение коммутативно;

2) х + х = 0;

3) кольцо не является областью целостности.

31. Доказать, что в определении кольца с единицей не обязательно требовать, чтобы операция «+» была коммутативной.

32. Доказать, что следующие подмножества являются подкольцами в кольце М_п(R):

1) диагональные матрицы;

2) верхнетреугольные матрицы.

33. Найти все подкольца колец вычетов Z₇, Z₁₀, Z₁₂.

34. Может ли в кольце, не являющемся полем, содержаться некоторое поле?

35. Показать, что эндоморфизмы абелевой группы образуют кольцо.

36. Показать, что биекция а+bÖ2 « а+bÖ3 не является изоморфизмом полей Q(Ö2),Q(Ö3) и что эти поля вообще неизоморфны.

37. Докажите, что Q(Ö2 + Ö3) = Q(Ö2 – Ö3) = Q(Ö2, Ö3).

38. Установить, что I – идеал кольца К. Является ли фактор-кольцо полем?

1) К ={а+bi | а,bÎZ}, I ={а + bi | a,b Î3Z}.

2) K={a+ bÖ2| a,bÎZ,}, I ={a + bÖ2| a,bÎ3Z}.

3) K=Z₃[x], I=(x² +1).

4) K=Z₂[x], I=(x² + х).

5) K=R[x], I=(x² +1).

39. Найдите идеал, порожденный множеством М, если

1) М ={3,5} в кольце Z;

2) М ={4,10} в кольце Z;

3) М ={х⁶–1,х⁴–1} в кольце R[x];

4) М ={х, х + 1} в кольце R[x].

40) Доказать, что фактор-кольцо R[x]/(x⁴ + x³ + х +1) не может быть полем ни для какого коммутативного кольца R.

41) Вычислить образ (2х + 1)^-1 в фактор-кольце F[x]/(x³– 2), где

1) F=Q;

2) F=Z₅;

3) F=F₇.

42. Доказать, что (x^m –1) |(xⁿ – 1) Û m |n над любым полем коэффициентов.

43. Является ли С[0,1] областью целостности? Показать, что отображение f®f(а) является эпиморфизмом, а ядро – максимальным идеалом.

44. Показать, что если р(х) приводим, то идеал (р(х)) немаксимален.

45. Показать, что х² + х + 1, х³ + х + 1, х⁴ + х + 1 неприводимы над F₂ и что нет других неприводимых многочленов 2-й и 3-й степени.

46. Составить таблицы умножения и сложения для колец Z₂[x]/(х² + х + 1), Z₂[x]/(х³ +х+1), Z₂[x]/( х³ + х² + 1).

47. Применив алгоритм Евклида, найти наибольшие общие делители многочленов с коэффициентами из поля F:

1) F=F₂, х⁷ + 1, х⁵ + х³ + 1;

2) F=F₂, х⁵ +x+ 1, х⁶ + х⁵ + х⁴ + 1;

3) F=F₃, х⁸ + 2х⁵ + х³ + х² + 1,2х⁶ + х⁵ + 2х³ + 2х² + 1;

48. Вычислить f(3), если f(х)=х²¹⁴ + 3х¹⁵² + 2х⁴⁷ + 2Î F₅[x].

49. Решить, если возможно, сравнения:

1) (х² + 1)f(х) = l(mod(x³ + 1)) в F₃[х];

2) (х⁴ + х³ + х² + 1)f(х) = х² + l(mod(x³ + 1)) в F₂[х].

50. Пусть f(х) Î F_p[x], тогда (f(x))^p= f(x^p). Доказать.

51. Доказать, что в коммутативном кольце характеристики р

Доказать неприводимость многочленов х² +1, х² + х + 4 над полем F₁₁ и построить изоморфизм фактор-колец

F₁₁[x]/(x² + 1) @ F₁₁[x]/(x² + x +4).

52. Найти порядки многочленов: х¹⁰ + x⁹ + x³ + x² ÎF₂[x],

х⁸ + х⁷ + х³ + х + 1 ÎF₂[x], x⁷ + х⁶ + x⁴ – х² + х ÎF₃[x],

(x² + х + l)⁵ (х³ + х + 1) ÎF₂[x]. Какие из них неприводимы?

53. Найти примитивный многочлен степени 6 над полем F₂.

54. Найти примитивный элемент a в Z[x]/(x² - 2), представить степени a²,...,a⁸ в виде а + bÖ2, a, b ÎF₃. Однозначноли такое представление?

55. Можно ли вложить F₄ в F₈?

56. Найти все примитивные элементы полей F₇, F₉, F₁₇.

57. Найти базис поля F₂₅ над простым подполем. Разложить все элементы по этому базису. Найти примитивный элемент a этого поля и для любого эле­мента b ÎF₂₅ найти п такое, что a = b^п.

58. Доказать, что если I – идеал кольца К, то I[x] – идеал кольца К[х].

59. Показать, что элемент Ö2 +i имеет степень 4 над Q и степень 2 над R. Найти его минимальные многочлены.

60. Доказать, что если многочлен F(х) неприводим в F_q[x], то F(aх+b) также неприводим, где a,b ÎF_q , a¹0,

61. Разложить многочлены на неприводимые множители: х⁹ + х+1 над F₂,

х⁷ + х⁶ + х⁵– х³ + х²–х–1 над F₃.

62. С помощью матриц дать представление для элементов поля F₈, используя многочлен х³ + х + 1. Дать аналогичное представление для F₁₆, F₉.

63. Доказать неприводимость многочлена х⁴ + х + 1 над F₂ и построить таблицы операций для его поля корня.

64. Показать, что поле корня х³ + х +1 над F₂ есть поле разложения.

65. Найти поля разложения (х² –3)(х³ +1) над Q, (х² –3)(х² –2х–2) над Q,

х³ + х + 1 над F₂.

66.Найти изоморфизм полей разложения х³ + 2х + 1 и х³ + 2х + 2 над F₃.

67. Найти степени неприводимых множителей многочлена х¹⁷ – 1 над F₂ и его поле разложения.

68. Установить примитивность многочленов x⁶ +x⁵+ x² +х+1 над F₂, x⁵ – х+1 над F₃.

69. Найти хотя бы один примитивный многочлен степени 3 над полем F₄.

70. Установить неприводимость, примитивность и найти порядок

х⁴ + х³ + х² – х – 1 над полем F₃.

71. Пусть A – любое множество автоморфизмов поля F. Показать, что элементы, инвариантные относительно всех а Î А, образуют подполе S(A)Ì F.

72. Над нолем F₂ рассматривается рекуррентное уравнение s_i – s_i-2 + s_i-3 =0. Вычислить периоды всех 8 последовательностей и их внутрипериодные значения.

73. Построить регистр сдвига с обратной связью, реализующий соотношение из предыдущею задания.

Тема 4. Классификация шифров

4.1. Классификация шифров по типу преобразова­ния

В качестве первичного признака, по которому произво­дится классификация шифров, используется тип преобразова­ния, осуществляемого с открытым текстом при шифровании. Если фрагменты открытого текста (отдельные буквы или группы букв) заменяются некоторыми их эквивалентами в шифртексте, то соответствующий шифр относится к классу шифров замены. Если буквы открытого текста при шифрова­нии лишь меняются местами друг с другом, то мы имеем дело с шифром перестановки. С целью повышения надежности шифрования шифрованный текст, полученный применением некоторого шифра, может быть еще раз зашифрован с помо­щью другого шифра. Все возможные такие композиции раз­личных шифров приводят к третьему классу шифров, которые обычно называют композиционными шифрами. Заметим, что композиционный шифр может не входить ни в класс шифров замены, ни в класс шифров перестановки. В результате полу­чаем первый уровень классификации шифров (рис. 3).

Рис. 3

4.2. Классификация шифров замены

Определим модель å_А=(X,K,Y,E,D) произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах А и В соответствен­но: хÌ.а*, YÌB*, ½A½=n, ½B½=m. Здесь и далее С* обозначает множество слов конечной длины в алфавите С.

Перед зашифрованием открытый текст предварительно представляется в виде последовательности подслов, называе­мых шифрвеличинами. При зашифровании шифрвеличины заменяются некоторыми их эквивалентами в шифртексте, ко­торые назовем шифробозначениями. Как шифрвеличины, так и шифробозначения представляют собой слова из А* и В* соответственно.

Пусть U = {u₁,...,u_N} – множество возможных шифрвеличин, V={v₁,...,v_M} – множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты xÎX, yÎY можно было представить словами из

U*, V* соответственно. Требование однозначности расшиф­рования влечет неравенства N ³ n, M ³ m, M ³ N.

Для определения правила зашифрования Е_k(х) в общем случае нам понадобится ряд обозначений и понятие распределителя, который, по сути, и будет выбирать в каждом такте шифрования замену соответствующей шифрвеличине.

Поскольку М ³ N , множество V можно представить в виде объединения непересекающихся непустых подмножеств V⁽ⁱ⁾. Рассмотрим произвольное семейство, со­стоящее из r таких разбиений множества V:

r Î N ,

и соответствующее семейство биекций

j_a : U®

для которых , i=1,…,N.

Рассмотрим также произвольное отображение y : К ´ N —> N*_r, где N_r = {1, 2,..., r}, такое, что для любых k Î К, l Î N

j= 1,...,l. (1)

Назовем последовательностьy(k,l) распределителем, отвечающим данным значениям k Î К, lÎ N.

Теперь мы сможем определить правило зашифрования произвольного шифра замены. Пусть

х Î X, х = х1,...хl, xÎU, i= 1,…,l; kÎ К

и Тогда Е_k(х) = у, где у = у₁…у_l,

j=1,…,l. (2)

В качестве у_j можно выбрать любой элемент множества . Всякий раз при шифровании этот выбор можно производить случайно, например, с помощью некоторого рандомизатора типа игровой рулетки.

Если ключ зашифрования совпадает с ключом расшифро­вания: k_з = k_р, то такие шифры называют симметричными,если же k_з ¹ k_р – асимметрич­ными.

В связи с указанным различием в использовании ключей сделаем еще один шаг в классификации (рис. 4).

Рис. 4

Отметим также, что в приведенном определении правило зашифрования Е_k(х) является, вообще говоря, многозначной функцией. Выбор ее значений представляет собой некоторую проблему, которая делает многозначные функции Е_k(х) не слишком удобными для использования. Избавиться от этой проблемы позволяет использование однозначных функций, что приводит к естественному разделению всех шифров заме­ны на однозначные и многозначные замены (называемых так­же в литературе омофонами).

Для однозначных шифров замены справедливо свойство:

для многозначных шифров замены:

Исторически известный шифр – пропорциональной за­мены представляет собой пример шифра многозначной заме­ны, шифр гаммирования – пример шифра однозначной заме­ны. Далее мы будем заниматься в основном изучением одно­значных замен, получивших наибольшее практическое при­менение. Итак, далее М = N и , i = 1,…,М .

Заметим, что правило зашифрования Е_k естественно "рассматривается как" отображение, Е_k :U* —> V *.

В силу инъективности (по k) отображения Е_k и того, что ½U½=½V½, введенные в общем случае отображения j_a явля­ются биекциями j_a :U « V, определенными равенствами , i=1,…,N, a=1,…,r.

Число таких биекций не пре­восходит N!.

Для шифра однозначной замены определение правила зашифрования можно уточнить: в формуле (2) включение следует заменить равенством

j=1,…,l. (2’)

Введем еще ряд определений.

Если для некоторого числа q Î N выполняются включе­ния v_i Î В^q, i=1,…,N, то соответствующий шифр замены бу­дем называть шифром равнозначной замены. В противном случае – шифром разнозначной замены (рис. 5).

Рис. 5

В подавляющем большинстве случаев используются шифры замены, для которых U Î А^p, для некоторого р Î N. При р=1 говорят о поточных шифрах замены, при р > 1 – о блочных шифрах замены (рис. 6).

Рис.6

Относительно деления шифров на поточные и блочные подробнее см. в Темах 5 и 6.

Следующее определение. В случае r = 1 шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае – многоалфавитным шифром замены (рис. 7).

Рис.7

Ограничиваясь наиболее важными классами шифров за­мены и исторически известными классами шифров переста­новки, сведем результаты классификации в схему, изобра­женную на рис.8.

Рис. 8

Прокомментируем приведенную схему. Подчеркнем, что стрелки, выходящие из любого прямоугольника схемы, указывают лишь на наиболее значимые частные подклассы шиф­ров. Пунктирные стрелки, ведущие из подклассов шифров перестановки, означают, что эти шифры можно рассматривать и как блочные шифры замены в соответствии с тем, что от­крытый текст делится при шифровании на блоки фиксиро­ванной длины, в каждом из которых производится некоторая перестановка букв. Одноалфавитные и многоалфавитные шифры могут быть как поточными, так и блочными. В то же время шифры гаммирования, образующие подкласс многоал­фавитных шифров, относятся к поточным, а не к блочным шифрам. Кроме того, они являются симметричными, а не асимметричными шифрами.

Далее мы рассмотрим свойства большинства из указан­ных на схеме классов шифров.

4.3 Шифры перестановки

В историческом обзоре упоминались некоторые типы шифров перестановки. Среди них – шифр Сцитола, атбаш, поворотная решетка Кардано. В самом общем виде шифр перестановки определен в гл. 3. Ключом шифра является пе­рестановка номеров букв открытого текста. Зависимость клю­ча от длины текста создает значительные неудобства в ис­пользовании шифра. В силу этого был предложен ряд частных шифров перестановок, которые можно применять для зашиф­рования текстов любой длины.