Размещено на http://www.allbest.ru/

Содержание

• Задание 1
• Задание 2
• Задание 3
• Задание 4
• Задание 5
• Задание 6
• Задание 7
• Задание 8
• Список использованных источников
• Задание 1
• Даны натуральные числа и . Найти их каноническое разложение. Вычислить их наибольший общий делитель и наименьшее общее кратное. Вычислить с помощью алгоритма Евклида. Выписать соотношение Безу для чисел и с помощью расширенного алгоритма Евклида.
• Решение.
• 1. Каноническое разложение чисел:
• и .
• 2. Наибольший общий делитель:
• .
• 3. Наименьшее общее кратное:
• .
• 4. Алгоритм Евклида. Вычисляем:
• следовательно, .
• 5. Соотношение Безу:
• .
• Найдем числа и с помощью расширенного алгоритма Евклида. В нашем случае: . Имеем:
• Окончательный результат: , т.е. .
• Задание 2
• зашифрованный тарабарский криптосообщение двоичный
• Вычислить для и из задания 1, где номер вашего варианта в данной контрольной работе.
• Решение
• Числа: , , .
• Определение. Функция Эйлера - количество чисел из совокупности , взаимно простых с числом . Если есть разложение, где - простые числа, то
• .
• Имеем:
• ,
• ,
• .
• Задание 3
• Построить таблицы сложения и умножения в кольце классов вычетов где m = 10 + k, k = 3. К каждому классу из указать обратный класс или обосновать его отсутствие. Сравнить количество всех обратимых классов с Циклична ли группа *?
• Решение.
• В нашем случае: .
• 1. Таблица сложения:

+

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[0]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[1]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[0]

[2]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[0]

[1]

[3]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[0]

[1]

[2]

[4]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[0]

[1]

[2]

[3]

[5]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[0]

[1]

[2]

[3]

[4]

[6]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[0]

[1]

[2]

[3]

[4]

[5]

[7]

[7]

[8]

[9]

[10]

[11]

[12]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[8]

[8]

[9]

[10]

[11]

[12]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[9]

[9]

[10]

[11]

[12]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[10]

[10]

[11]

[12]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[11]

[11]

[12]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[12]

[12]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

• 2. Таблица умножения:

*

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[0]

[0]

[0]

[0]

[0]

[0]

[0]

[0]

[0]

[0]

[0]

[0]

[0]

[0]

[1]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[2]

[0]

[2]

[4]

[6]

[8]

[10]

[12]

[1]

[3]

[5]

[7]

[9]

[11]

[3]

[0]

[3]

[6]

[9]

[12]

[2]

[5]

[8]

[11]

[1]

[4]

[7]

[10]

[4]

[0]

[4]

[8]

[12]

[3]

[7]

[11]

[2]

[6]

[10]

[1]

[5]

[9]

[5]

[0]

[5]

[10]

[2]

[7]

[12]

[4]

[9]

[1]

[6]

[11]

[3]

[8]

[6]

[0]

[6]

[12]

[5]

[11]

[4]

[10]

[3]

[9]

[2]

[8]

[1]

[7]

[7]

[0]

[7]

[1]

[8]

[2]

[9]

[3]

[10]

[4]

[11]

[5]

[12]

[6]

[8]

[0]

[8]

[3]

[11]

[6]

[1]

[9]

[4]

[12]

[7]

[2]

[10]

[5]

[9]

[0]

[9]

[5]

[1]

[10]

[6]

[2]

[11]

[7]

[3]

[12]

[8]

[4]

[10]

[0]

[10]

[7]

[4]

[1]

[11]

[8]

[5]

[2]

[12]

[9]

[6]

[3]

[11]

[0]

[11]

[9]

[7]

[5]

[3]

[1]

[12]

[10]

[8]

[6]

[4]

[2]

[12]

[0]

[12]

[11]

[10]

[9]

[8]

[7]

[6]

[5]

[4]

[3]

[2]

[1]

• 3. По таблице умножения легко можно найти обратные классы: берем столбец с элементом и ищем в нем элемент [1], предположим, это будет строка . Тогда . Для тех элементов, в столбцах которых нет класса [1] нет и обратного класса. Итак:

класс	обратный класс
[1]	[1]
[2]	[7]
[3]	[9]
[4]	[10]
[5]	[8]
[6]	[11]
[7]	[2]
[8]	[5]
[9]	[3]
[10]	[4]
[11]	[6]
[12]	[12]

• Для класса , представитель которого не является взаимно простым с числом 13, нет обратного класса. Необратимые классы: все от [1] до [12].
• 4. Вычисляем: - количество чисел из совокупности , взаимно простых с числом . В нашем случае числа, взаимно простые с 13 - это все числа 1 до 12. Следовательно, . Число совпадает с количеством классов, имеющих обратный класс (т.е. обратимых).
• 5. Мультипликативная группа ненулевых элементов является цикличной, так как в группе есть элемент, являющийся порождающим, т.е. любой элемент группы можно получить возведением в некоторую степень этого порождающего элемента. Если у таблице умножения есть столбец (строка), содержащая все элементы группы, то соответствующий элемент является порождающим. В нашем случае, например, b=[2]:
• , , , , , и т.д.
• Задание 4
• Установить истинное сообщение, зашифрованное классическим методом.
• а) расшифровать криптограмму Цезаря:
• цълхзфя еогфхесегхя фсдсм.г.ф.тцынлр
• Решение.
• Пронумеруем каждую букву алфавита. Прибавим к каждому числу число . Результат записываем по модулю 33. Путем подбора нашли, что .

ц	24		21	у
ъ	28		25	ч
л	13		10	м
х	23		20	т
з	9		6	е
ф	22		19	с
я	33		30	ь
е	6		3	в
о	16		13	л
г	4		1	а
ф	22		19	с
х	23		20	т
е	6		3	в
с	19		16	о
е	6		3	в
г	4		1	а
х	23		20	т
я	33		30	ь
ф	22		19	с
с	19		16	о
д	5		2	б
с	19		16	о
м	14		11	й
.			.
г	4		1	а
.			.
ф	22		19	с
.			.
т	20		17	п
ц	24		21	у
ы	29		26	ш
н	15		12	к
л	13		10	и
р	18		15	н

• Расшифрованный текст:
• «Учитесь властвовать собой. А.С. Пушкин»
• б) перевести с тарабарского:
• па цшойпор лкетсе уфомы пагемкис ромоф
• Решение.
• В тарабарской грамоте шифром являлся алфавит, буквы которого записывались в две строчки, одна за другой, и взаимозаменялись.
• Заменяем только согласные - без буквы «й», получаем такое соответствие:

б	щ
в	ш
г	ч
д	ц
ж	х
з	ф
к	т
л	с
м	р
н	п

• Получаем:
• «На двойном стекле узоры начертил мороз».
• в) расшифровать текст, зашифрованный с помощью девиза «Роза»:
• гэнвсяиесысрезсоьшцбщпхжвчбйцячмр
• Решение.
• Разобьем текст на «слова» по 4 буквы:
• гэнв сяие сыср езсо ьшцб щпхж вчбй цячм р
• Пронумеруем каждую букву в алфавите:

1	а
2	б
3	в
4	г
5	д
6	е
7	ё
8	ж
9	з
10	и
11	й
12	к
13	л
14	м
15	н
16	о
17	п
18	р
19	с
20	т
21	у
22	ф
23	х
24	ц
25	ч
26	ш
27	щ
28	ъ
29	ы
30	ь
31	э
32	ю
33	я

• Получаем: РОЗА = 18 16 9 1.
• Алгоритм расшифровки такой: из номера по порядку для буквы зашифрованного слова вычитаем номер по порядку буквы девиза. Это делаем для каждого «слова» в данном тексте. Например:
• «г» имеет номер 4, «Р» - номер 18, далее: 4 - 18 mod 33 = 19, что соответствует букве «с».
• Получаем:

г	4	18	19	с		е	6	18	21	у		в	3	18	18	р
э	31	16	15	н		з	9	16	26	ш		ч	25	16	9	з
н	15	9	6	е		с	19	9	10	и		б	2	9	26	ш
в	3	1	2	б		о	16	1	15	н		й	11	1	10	и
с	19	18	1	а		б	30	18	12	к		ц	24	18	6	е
я	33	16	17	п		ш	26	16	10	и		я	33	16	17	п
и	10	9	1	а		ц	24	9	15	н		ч	25	9	16	о
е	6	1	5	д		б	2	1	1	а		м	14	1	13	л
с	19	18	1	а		щ	27	18	9	з		р	18	18	0	я
ы	29	16	13	л		п	17	16	1	а
с	19	9	10	и		х	23	9	14	м
р	18	1	17	п		ж	8	1	7	ё

• Здесь в первом столбце - зашифрованные слова, во втором - номер буквы в алфавите, в третьем - номера букв в алфавите для слова «роза», в четвертом - разность чисел второго и третьего столбцов по модулю 33.
• Выделенные буквы - это расшифрованное выражение.
• Получаем:
• «С неба падали пушинки на замёрзшие поля».
• Применяли шифр Виженера.
• г) Прочитать текст, зашифрованный методом постолбцовой транспозиции (n=5, m=6).
• кпяез вчтоо ниьсп ыисее цлуал иртла
• Решение.
• Запишем текст по столбцам «змейкой» в прямоугольник 5 на 6:

к	о	н	е	ц	А
п	о	и	е	л	л
я	т	ь	с	у	т
е	ч	с	и	а	р
з	в	п	ы	л	и

• Читаем теперь построчно «змейкой», получаем:
• «Конец аллеи опять с утра исчез в пыли».
• Задание 5
• Расшифровать криптосообщение RSA:
• {ш;е;n}={1205;11;1517}.
• Решение.
• Число можно единственным способом представить как произведение двух простых чисел , т.е. и , следовательно,
• .
• Найдем такое число , для которого выполняется:
• Таким числом является .
• Расшифрованное сообщение:
• .
• Вычисления: .
• Имеем:
• ,
• ,
• ,
• .
• Ответ. .
• Задание 6
• Расшифровать криптосообщение Эль Гамаля:
• {m;O;P;g;h;x}={15;14;37;13;6;9}.
• Решение.
• Вычисляем:
• .
• Находим в поле , т.е. такое число, что
• .
• Это будет число .
• Истинное сообщение:
• .
• Ответ.
• Задание 7
• Убедиться в неприводимости и примитивности данного полинома пятой степени с коэффициентами из Сформировать с помощью этого полинома поле Галуа из 32-х элементов. Выписать проверочную матрицу примитивного двоичного БЧХ-кода длиной 31, исправляющего двойные ошибки.
• Решение.
• 1. Полином является неприводимым, если из разложения следует, что или являются константами. Проверим неприводимость данного многочлена над полем .
• а) , , следовательно, данный полином не имеет корней, а поэтому и делителей степени 1.
• б) Известна теорема: полином степени 2 или 3 неприводим тогда и только тогда, когда он не имеет корней в поле . Отсюда следует, что единственным неприводимым полиномом степени 2 над полем является .
• Проверим, делится ли данный полином на многочлены степени 2. Так как мы степень 1 проверили, то надо делить только на неприводимые полиномы степени 2, т.е. на . Имеем:
• ,
• следовательно, не делится без остатка на .
• в) Делимость без остатка многочлена на многочлены других степеней (3 и 4 в нашем случае проверять не надо, т.к. достаточно было проверить до степени .
• Итак, данный многочлен является неприводимым надо полем .
• 2. Проверим примитивность многочлена.
• а) Известно, что порядок многочлена делит число . А т.к. число 31 простое, то порядок данного многочлена равен: .
• б) .
• Отсюда следует (по соответствующей теореме), что данным многочлен является примитивным.
• 3. Сформируем с помощью этого полинома поле Галуа из 32-х элементов.
• В таблице задано представление поля GF(32) как расширение поля GF(2), построенное по примитивному полиному . Для этого записываем число , в виде полинома, искомый элемент поля - это остаток полученного полинома на .
• Например:
• ,
• следовательно, получаем соответствующий элемент: . В двоичном виде он записывается как 01111, в десятичном виде равен числу
• .
• Получаем:

В виде степени	В виде многочлена	В двоичном виде	Десятичное обозначение
0	0	00000	0
x^0	1	00001	1
x^1	x	00010	2
x^2	x^2	00100	4
x^3	x^3	01000	8
x^4	x^4	10000	16
x^5	x^3+x^2+x+1	01111	15
x^6	x^4+x^3+x^2+x	11110	30
x^7	x^4+x+1	10011	19
x^8	x^3+1	01001	9
x^9	x^4+x	10010	18
x^10	x^3+x+1	01011	11
x^11	x^4+x^2+x	10110	22
x^12	x+1	00011	3
x^13	x^2+x	00110	6
x^14	x^3+x^2	01100	12
x^15	x^4+x^3	11000	24
x^16	x^4+x^3+x^2+x+1	11111	31
x^17	x^4+1	10001	17
x^18	x^3+x^2+1	01101	13
x^19	x^4+x^3+x	11010	26
x^20	x^4+x^3+x+1	11011	27
x^21	x^4+x^3+1	11001	25
x^22	x^4+x^3+x^2+1	11101	29
x^23	x^4+x^2+1	10101	21
x^24	x^2+1	00101	5
x^25	x^3+x	01010	10
x^26	x^4+x^2	10100	20
x^27	x^2+x+1	00111	7
x^28	x^3+x^2+x	01110	14
x^29	x^4+x^3+x^2	11100	28
x^30	x^4+x^2+x+1	10111	23

• 4. Обозначим: - количество ошибок, которые исправляет код. Исходя из определения БЧХ-кода над длины 31, корнями порождающего многочлена являются степени с 1 по примитивного элемента : . Порождающий многочлен находится по формуле:
• ,
• где - минимальный полином корня , . Минимальный многочлен элемента поля определяется так:
• ,
• где - наименьшее число, при котором .
• Значения минимальных многочленов будут следующими:
• ,
• .
• Получаем:
• .
• Проверочный полином находится из выражения:
• .
• Проверочная матрица строится так:
• .
• В нашем случае эта матрица будет состоять из 31 столбца и 10 строк:

0	0	0	0	1	0	1	1	0	1	0	1	0	0	0	1	1	1	0	1	1	1	1	1	0	0	1	0	0	1	1
0	0	0	1	0	1	1	0	1	0	1	0	0	0	1	1	1	0	1	1	1	1	1	0	0	1	0	0	1	1	1
0	0	1	0	0	1	1	0	0	0	0	1	0	1	1	0	1	0	1	0	0	0	1	1	1	0	1	1	1	1	0
0	1	0	0	0	1	1	1	0	1	1	1	1	1	0	0	1	0	0	1	1	0	0	0	0	1	0	1	1	0	1
1	0	0	0	0	1	0	1	1	0	1	0	1	0	0	0	1	1	1	0	1	1	1	1	1	0	0	1	0	0	1
0	0	1	1	0	1	0	1	0	0	1	0	0	0	1	0	1	1	1	1	1	0	1	1	0	0	1	1	1	0	0
0	1	1	0	0	1	1	1	0	0	1	0	1	1	0	1	0	1	0	0	1	0	0	0	1	0	1	1	1	1	1
0	0	1	0	0	0	1	0	1	1	0	1	1	0	1	1	0	0	1	1	1	0	0	0	0	1	1	0	1	0	1
0	0	1	1	1	0	0	0	0	1	1	0	1	0	1	0	0	1	0	0	0	1	0	1	1	1	1	1	0	1	1
1	0	0	0	1	0	1	1	1	1	1	0	1	1	0	0	1	1	1	0	0	0	0	1	1	0	1	0	1	0	0

• Задание 8
• Аппарат сотовой связи с кодом из задания 7 принял сообщение . Убедиться, что сообщение содержит ошибки.
• Решение.
• Сообщение содержит ошибки, если , где - проверочная матрица кода.
• Вычисляем: , следовательно, доказали, что сообщение содержит ошибку.

Список использованных источников

1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. - 120с.

2. Цапенко М.П. Измерительные информационные системы. - М.: Энергоатом издат, 2005. - 440с.

3. Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. -368 с.

4. Блейхут Р. Теория и практика кодов, контролирующих ошибки. 1986. 576 с.

Размещено на Allbest.ru

...