Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Теория чисел (расчётка).doc
Скачиваний:
91
Добавлен:
16.12.2018
Размер:
870.91 Кб
Скачать

28

ВВЕДЕНИЕ …………………………………………………………….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

Введение

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

  • представление данных проищвольной формы в памяти компьютера;

  • обеспечение помехоустойчивости при передаче информации по каналам связи;

  • сжатие информации в базах данных;

  • защита информации от несанкционированного доступа.

В алгоритмах защиты информации широко используется модулярная арифметика. А при кодировании для обеспечения помехоустойчивости – вычисления в конечных полях. Данные вопросы рассматриваются в теории чисел.

  1. Элементы теории чисел

    1. Модулярная арифметика

Модулярная арифметика часто называется “арифметикой часов”. Если прибавить 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 делит (ab)”.

Если 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, целесообразно использовать алгоритмы быстрого возведения в степень.