- •Введение
- •Элементы теории чисел
- •Модулярная арифметика
- •Алгоритм Евклида для нахождения наибольшего общего делителя
- •Вычисление обратных величин
- •Основные способы нахождения обратных величин
- •Расширенный алгоритм Евклида
- •Китайская теорема об остатках
- •Квадратичные вычеты
- •Вычисления в конечных полях
- •Свойства многочленов в двоичном поле gf(2)
- •Достоинства вычислений в поле Галуа gf(2 n)
- •Кодирование
- •Оптимальное кодирование
- •Обнаружение и исправление ошибок
- •Общие понятия
- •Линейные групповые коды
- •Код Хэмминга
- •Циклические коды
- •Построение и декодирование конкретных циклических кодов
- •Циклические коды, исправляющие две и большее количество ошибок, d0 5
- •Сжатие информации
- •Исключение повторения строк в последующих строках
- •Алгоритм lzw
- •Задания для самостоятельного выполнения
- •Расчетно-графическая работа №1
- •Расчетно-графическая работа №2
- •Список рекомендуемой литературы
- •Рекомендованная литература
ВВЕДЕНИЕ …………………………………………………………….4
1 ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ 4
1.1 Модулярная арифметика 4
1.2 Алгоритм Евклида для нахождения наибольшего общего делителя 7
1.3 Вычисление обратных величин 9
1.4 Основные способы нахождения обратных величин 12
1.5 Расширенный алгоритм Евклида 14
1.6 Китайская теорема об остатках 15
1.7 Квадратичные вычеты 17
1.8 Вычисления в конечных полях 19
1.9 Свойства многочленов в двоичном поле GF(2) 21
1.10 Достоинства вычислений в поле Галуа GF(2 n) 26
2 КОДИРОВАНИЕ 27
2.1 Оптимальное кодирование 27
3 ОБНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК 34
3.1 Общие понятия 34
3.2 Линейные групповые коды 35
3.3 Код Хэмминга 42
3.4 Циклические коды 46
3.5 Построение и декодирование конкретных циклических кодов 52
3.5.1 Коды исправляющие одиночную ошибку d0 = 3 52
3.5.2 Циклические коды, исправляющие две и большее количество ошибок, d0 5 57
4 СЖАТИЕ ИНФОРМАЦИИ 61
4.1 Исключение повторения строк в последующих строках 61
4.2 Алгоритм LZW 65
5 ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ 65
5.1 Расчетно-графическая работа №1 65
5.2 Расчетно-графическая работа №2 68
6 СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ 73
7 РЕКОМЕНДОВАННАЯ ЛИТЕРАТУРА 73
Введение
Ранее средства кодирования играли вспомогательную роль и не рассматривались как отдельный предмет математического изучения. Но с появлением компьютеров ситуация радикально изменилась. Кодирование буквально пронизывает информационные технологии и является центральным вопросом при решении самых разных задач программирования:
-
представление данных проищвольной формы в памяти компьютера;
-
обеспечение помехоустойчивости при передаче информации по каналам связи;
-
сжатие информации в базах данных;
-
защита информации от несанкционированного доступа.
В алгоритмах защиты информации широко используется модулярная арифметика. А при кодировании для обеспечения помехоустойчивости – вычисления в конечных полях. Данные вопросы рассматриваются в теории чисел.
-
Элементы теории чисел
-
Модулярная арифметика
Модулярная арифметика часто называется “арифметикой часов”. Если прибавить 14 часов к 3 часам после полудня, то получится 5 часов утра следующего дня:
3 + 14 5 (mod 12)
или
(3 + 14) mod 12 = 5.
Это арифметика по модулю 12.
Обычная запись в модулярной арифметике
a b (mod n)
читается так: “a сравнимо с b по модулю n”.
Это соотношение справедливо для целых значений a, b и n 0, если и только если
а = b + k • n
для некоторого целого k.
Отсюда, в частности , следует
n | (a ─ b).
Это читается как “n делит (a ─ b)”.
Если a b (mod n), то b называют вычетом числа a по модулю n.
Операцию нахождения вычета числа а по модулю n
a (mod n)
называют приведением числа а по модулю n или приведением по модулю.
В нашем примере
(3 + 14) mod 12 = 17 mod 12 = 5
или
17 5 (mod 12),
число 5 является вычетом числа 17 по модулю 12.
Набор целых чисел от 0 до (n – 1) называют полным набором вычетов по модулю n.
Это означает, что для любого целого а (а > 0) его вычет r по модулю n есть некоторое целое число в интервале от 0 до (n – 1), определяемое из соотношения
r = a – k • n,
где k – целое число.
Например, для n = 12 полный набор вычетов:
{0, 1, 2, … , 11}.
Обычно используют вычеты
r {0, 1, 2, … , n – 1},
но иногда полезны вычеты в диапазоне целых:
r {– ½ (n – 1), … , ½ (n – 1)}.
Важно, что
– 12 (mod 7) – 5 (mod 7) 2 (mod 7) 9 (mod 7) и т.д.
Модулярная арифметика аналогична во многом обычной арифметике: она коммутативна, ассоциативна и дистрибутивна. Точнее говоря, целые числа по модулю n с использованием ипераций сложения и умножения образуют коммутативное кольцо при соблюдении законов ассоциативности, коммутативности и дистрибутивности.
Фактически можно сначала приводить по модулю n, а затем выполнять операции, либо сночала выполнять операции, а затем приводить по модулю n, поскольку приведение по модулю n является гомоморфным отображением из кольца целых в кольцо целых по модулю n:
(a + b) mod n = [ a (mod n) + b (mod n) ] mod n,
(a b) mod n = [ a (mod n) b (mod n) ] mod n,
(a • b) mod n = [ a (mod n) • b (mod n) ] mod n,
[a • (b + c) ] mod n = {[a • b (mod n) ] + [a • c (mod n) ]} mod n.
Криптография использует множество вычислений по модулю n, потому что задачи типа вычисления дискретных логарифмов и квадратных корней очень трудны.
Кроме того, с вычислениями по модулю удобнее работать, потому что они ограничивают диапазон всех промежуточных величин и результата.
Для модуля n длиной k бит промежуточные результаты любого сложения, вычитания или умножения будут не длиннее 2kбит. Поэтому возведение в степень в модулярной арифметике можно выполнить без генерации очень больших промежуточных результатов.
Вычисление степени числа а по модулю n
а х mod n
можно выполнить как ряд умножений и делений. Существует способ сделать это быстрее. Поскольку эти операции дистрибутивны, быстрее произвести возведение в степень как ряд последовательных умножений, выполняя каждый раз приведение по модулю. Это особенно заметно, если работать с длинными числами (200 бит и более).
Пример. Нужно вычислить а 8 mod n.
Не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:
(а • а • а • а • а • а • а • а) mod n.
Вместо этого выполняют три малых умножения и три малых приведения по модулю:
((а 2 mod n.)2 mod n.)2 mod n.
Тем же способом вычисляют
а 16 mod n. = (((а 2 mod n.)2 mod n.)2 mod n.)2 mod n.
Вычисление
а х mod n,
где х не является срепенью 2, лишь немного сложнее. Двоичная запись числа х позволяет представить число х как сумму степеней 2:
х = 12 (10) = 11001 (2).
Поэтому 25 = 2 4 + 2 3 + 2 0.
Тогда
а 25 mod n. = (а • а 24) mod n. = (а • а 8 • а 16) mod n =
= (а • ((а 2) 2) 2 • (((а 2) 2) 2 ) 2) mod n = ((((а 2 • а) 2) 2 ) 2 • а) mod n.
При разусном накоплении промежуточных результатов потребуется только шесть умножений:
(((((((а 2 mod n) • а) mod n)2 mod n)2 mod n)2 mod n) • а) mod n.
Этот метод уменьшает трудоемкость вычислений до 1,5хk операций в стреднем, где k – длина числа в битах.
Поскольку многие алгоритмы шифрования основаны на возведении в степень по модулю n, целесообразно использовать алгоритмы быстрого возведения в степень.