Упражнения

Раздел 4.1

1. Покажите, что в векторном пространстве размерности над GF(2) расстояние Хэмминга — это метрика, а вес Хэмминга — норма.

2. Завершите доказательство лемм 4.1.5 и 4.1.9.

3. Покажите, что если кодовое расстояние +1, то этот код может исправлять ошибок и обнаруживать +1 ошибок.

4. Постройте код, состоящий из восьми слов длины 7, такой, что расстояние между любыми двумя различными кодовыми словами не меньше 4.

Раздел 4.1.1

1. Пусть

— порождающая матрица двоичного (-кода. Определите его проверочную матрицу, кодовые слова и лидеры смежных классов для этого кода.

2. При помощи (-кода Хэмминга с проверочной матрицей

закодируйте сообщения (0,1,1,0) и (1,0,1,0). Кроме того, предполагая, что случилось не более одной ошибки, декодируйте векторы которые были получены по зашумленному каналу.

3. Модификация проверочной матрицы Н из упр. 2 позволяет нам обнаруживать наличие двух ошибок, а также исправлять одну ошибку. А именно, добавляя столбец нулей в начале (слева) и заполняя верхнюю строку единицами, мы получаем

Теперь если v — полученный вектор, и — переданный и , то:

a. Если все координаты равны нулю, то при передаче не было ошибок.

b. Если имеет одну ненулевую координату, то встретилась одна ошибка, и она находится так же, как в упр. 2.

c. Если имеет два ненулевых элемента, то случились две ошибки.

В последнем случае сумма двух столбцов матрицы Н, но определить, какие два столбца матрицы Н дают эту сумму, нельзя. Можно, однако, утверждать, что не является столбцом матрицы Н, поскольку сумма двух столбцов матрицы Н всегда имеет верхний элемент

Декодируйте векторы

предполагая, что в каждом из них имеются 0, 1 или 2 ошибки.

Существуют ли в (-коде Хэмминга полученные слова, для которых получатель может с уверенностью утверждать, что они имеют по крайней мере 3 ошибки?

4. Покажите, что — -код Хэмминга совершенен.

5. Двоичные коды можно обобщить на коды, которые являются векторными пространствами над любым конечным полем Пусть

— порождающая матрица троичного (-кода С. Найдите его проверочную матрицу.

Раздел 4.1.2

1. Определите все кодовые слова кода с порождающим полиномом над GF(2), если длина сообщений равна 4. Имеет ли (0,1,1,1,0,1,1) обнаруживаемые ошибки?

2. Полином является порождающим полиномом циклического кода над GF(2) с блоками длины 15. Найдите проверочный полином и порождающую и проверочную матрицы этого кода. Сколько ошибок может исправлять этот код?

3. Проверьте, что двоичный полином неприводим, и, используя это, постройте матрицу Н для

БЧХ-кода, исправляющего две ошибки, с блоками длины 15, имеющими 7 информационных и 8 проверочных битов.

4. Рассмотрим циклический (-код с ) Является ли кодовым словом, и если нет, то каков его синдром?

5. Покажите, что схема, изображенная на рис. 4.1.5, действительно производит кодовые слова кода, для которого является проверочным полиномом. Постройте такую схему кодирования для частного случая двоичного (-кода Хэмминга с )

6. [Кодирование циклическим (-кодом, использующим регистры с разрядами.] Пусть ) — полином степени , коэффициенты которого при к наивысших степенях а именно являются к информационными битами, а остальные коэффициенты равны 0. Если — полином степени , то по алгоритму деления получаем Тогда — полином степени делящийся на который можно рассматривать как кодовое слово циклического -кода, порожденного полиномом Спроектируйте схему кодирования, использующую регистр с п — к разрядами, основанную на приведенных рассуждениях.

7. Спроектируйте схему для обнаружения ошибок циклического кода.

Раздел 4.2.1

1. Покажите, что отображение а из в себя инъективно тогда и только тогда, когда

2. Используйте «computer» как ключ в коде Виженера и зашифруйте слово «cryptography».

3. Получите случайную последовательность подбрасыванием монетки и используйте эту последовательность в одноразовом блокноте, чтобы зашифровать сообщение «secret code».

4. Используя данный в тексте квадрат Плайфера, зашифруйте слово «university».

5. Покажите, что то М — матрица инволюции тогда и только тогда, когда Постройте матрицу инволюции, у которой

6. Пусть алфавит открытого и шифрованного текстов в шифре Хилла. Пусть

— матрица шифрования. Зашифруйте слово «department». Чему равна обратная к К матрица?

7. В -буквенном алфавите, описанном в тексте, воспользуйтесь модулярным шифром с чтобы зашифровать сообщение «congratulations».

8. Пользуясь таблицей относительных частот на рис. 4.2.2, дешифруйте следующее сообщение, про которое известно, что оно зашифровано с использованием модулярного шифра при (известного также как сдвиг):

9. Предположим, что мы все еще работаем с -буквенным алфавитом, но теперь в модулярном шифре. Более того, наиболее часто в шифрованном тексте встречается буква а вторая по частоте — буква Пользуясь информацией из рис. 4.2.2, что в английском языке — две наиболее часто встречающиеся буквы, выведите формулу для дешифровки сообщения. (Указание. Если — символ открытого текста, — символ шифрованного текста, то вам нужно найти , к такие, что ); — это мультипликативный обратный к , где — параметры модулярного шифра.)

10. а. Сколько модулярных шифров имеется в -буквенном

алфавите в случае

В общем случае сколько модулярных шифров имеется в -буквенном алфавите?

c. Сколько модулярных шифров имеется, когда

11. Предположим, что мы используем модулярный шифр ( в -буквенном алфавите. Буква называется неподвижной, если ).

а. Покажите, что если — простое число, то всегда существует неподвижная буква.

b. Покажите, что если в нашем модулярном шифре то (для любого ) имеется по крайней мере одна неподвижная буква, более того, если m четно то имеются по крайней мере две неподвижные буквы.

Раздел 4.2.2

1. Пользуясь криптосистемой рюкзака, зашифруйте слово «university». Используйте те же присвоения букв и те же параметры, что и в соответствующем примере в тексте.

2. Завершите пример, данный в тексте, для RSA-криптосис-темы.

3. В упр. 19 разд. 2.3.3 мы видели, что если мы найдем основание b, такое, что псевдопросто, но не строго псевдопросто по основанию b, то мы можем быстро найти нетривиальный сомножитель числа . Объясните, как бороться с этим при выборе в RSA-криптосистеме.

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

5. Покажите, что супервозрастающая последовательность с наименьшими значениями — это последовательность Покажите затем, что соответствующая задача рюкзака всегда имеет решение , а именно и что нет никакой другой супервозрастающей последовательности, для которой соответствующая задача рюкзака всегда имеет решение.

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

7. (Бросание монеты на большом расстоянии с использованием двулистной односторонней функции.) Предположим, что при подготовке международного футбольного матча представители двух команд решили без проведения личной встречи «бросить монетку», чтобы определить, в какой стране провести игру.

Под двулистной односторонней функцией мы подразумеваем алгоритм, который:

a. по данному ключу Е подходящего типа строит функцию , такую, что для каждого элемента с существует ровно два элемента , таких, что . по данному ключу D («обратному» к Е) и с можно найти оба значения , такие, что

Мы предполагаем, что, зная только Е, вычислительно невозможно найти D (см. ниже упр. 8). Отсюда следует, что для данного можно найти «сопутствующий» элемент такой, что если известны и Е, и

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

8. В упр. 23 разд. 3.3.1 был представлен алгоритм решения сравнения для любого простого числа и квадратичного вычета а. (См. также упр. 1 по программированию разд. 3.3.1.) Предположим, однако, что нет хорошего алгоритма решения сравнения , где а — квадратичный вычет по модулю n, а произведение двух различных больших простых чисел, если нам не известно разложение на множители (если оно известно, то для нахождения квадратного корня по модулю по данным квадратным корням по модулям используется греко-китайский алгоритм). Предположим, что не оба числа сравнимы с по модулю 4, и (как в упр. 7) пусть и пусть — множество пар вычетов по модулю . Рассмотрите функцию и покажите, что таким образом получается пример из упр. 7 реализации бросания монеты на большом расстоянии.

9. (-криптосистема не всегда скрывает сообщения.) Пусть — произвольное целое число, являющееся произведением простых (т.е. свободно от квадратов). Пусть d и — положительные целые числа, такие, что для

любого простого , такого, что пусть Покажите, что для любого целого а (имеет ли оно общий сомножитель с или нет).