Криптография базируется на некоторых специфических областях математики, включая теорию чисел, линейную алгебру и алгебраические структуры. В этой лекции мы обсуждаем только те темы в вышеупомянутых областях, которые необходимы для понимания содержания следующих нескольких лекций. Читатели, которые знакомы с этими темами, могут пропустить лекцию полностью или частично. Подобные теоретические лекции встречаются всюду в этом курсе, когда это необходимо.
В арифметике целых чисел мы используем множество целых чисел и несколько операций. Вы знакомы с этим множеством и соответствующими операциями, но они рассмотрены здесь, чтобы объяснить потом основы действий со сравнениями по модулю m.
Множество целых чисел, обозначенных Z, содержит все числа (без дробей) от минус бесконечности до плюс бесконечности (рис. 2.1).
(рис 2.1) Множество целых чисел
В криптографии нас интересует три a и b ) и выход ( c ), как это показано на рис. 2.2. Два входа принимают числа из множества целых чисел; выход выводит результат операции — число из множества целых чисел.
Обращаем внимание, что деление не относится к этой категории операций, потому что мы скоро убедимся, что этой операции нужны два выхода вместо одного.
(рис 2.2) Три бинарных операции для множества целых чиселПример 2.1
Следующие примеры показывают результаты трех бинарных операций на множестве двух целых чисел. Поскольку каждый вход может быть или положителен или отрицателен, мы имеем четыре случая для каждой операции.
Сложение 5+9=14 (-5)+9=4 5+(-9)=-4 (-5)+(-9)=-14 Вычитание 5-9=-4 (-5)-9=-14 5 - (-9)=14 (-5)- (-9)=+4 Умножение 5 x 9=45 (-5) x 9=-45 5 x (-9)=-45 (-5) x (-9)=45
В арифметике целых чисел, если мы a делим на n, мы можем получить q и r. Отношения между этими четырьмя целыми числами можно показать как
В этом равенстве a называется делимое ; q — частное ; n — делитель и r — остаток. Обратите внимание, что это — не операция, поскольку результат деления a на n — это два целых числа, q и r. Мы будем называть это уравнением деления.
Пример 2.2
Предположим, что a = 255, а n = 23. Мы можем найти q = 11 и r = 2, используя алгоритм деления, мы знаем из элементарной арифметики — оно определяется, как показано на рис. 2.3.
(рис 2.3) Пример 2.2, нахождение частного и остаткаБольшинство компьютерных языков может найти частное и остаток, используя заданные языком операторы. Например, на языке C оператор "/" может найти частное, а оператор "%" — остаток.
Когда мы используем вышеупомянутое уравнение деления в криптографии, мы налагаем два ограничения. Первое требование: чтобы делитель был положительным целым числом ( n > 0 ). Второе требование: чтобы остаток был неотрицательным целым числом ( r >= 0 ). Рисунок 2.4 показывает эти требования с двумя указанными ограничениями.
(рис 2.4) Алгоритм деления целых чиселПример 2.3
Предположим, мы используем компьютер или калькулятор, а r и q отрицательны, при отрицательном a. Как можно сделать, чтобы выполнялось ограничение, что число r должно быть положительным? Решение простое: мы уменьшаем значение q на 1 и добавляем значение n к r, чтобы r стало положительным.
Мы уменьшили ( –23 ), получили ( –24 ) и добавили 11 к ( –2 ), чтобы получить + 9. Полученное равенство эквивалентно исходному.
Мы можем изобразить рассмотренные выше уравнения с двумя ограничениями на n и r на рис. 2.5 с помощью двух графов. Первый показывает случай, когда число a положительно; второй — когда отрицательно.
(рис 2.5) Граф алгоритма деленияГраф начинается с нуля и показывает, как мы можем достигнуть точки, представляющей целое число a на линии. В случае положительного a мы должны перемещаться на величину $$q \times n$$ направо и затем добавить дополнительную величину r в том же самом направлении. В случае отрицательного a мы должны двигаться на величину $$(q - 1) \times n$$ налево (число q в этом случае отрицательно) и затем дополнять число r в противоположном для указанного выше движения направлении. В обоих случаях значение r положительно.
Теперь кратко обсудим теорию делимости — тема, с которой мы часто сталкиваемся в криптографии. Если a не равно нулю, а r = 0, в равенстве деления мы имеем
a = q x nМы тогда говорим, что a делится на n (или n — делитель a ). Мы можем также сказать, что a делится без остатка на n. Когда мы не интересуемся значением q, мы можем записать вышеупомянутые отношения как n|a. Если остаток не является нулевым, то n не делит, и мы можем записать отношения как n†a.
Пример 2.4
a. Целое число 4 делит целое число 32, потому что $$32=8 \times 4$$. Это можно отобразить как 4|32. Число 8 не делит число 42, потому что $$42 = 5 \times 8 + 2$$. В этом уравнении число 2 — остаток. Это можно отобразить как 8†42.
Пример 2.5
а. Отображение 13|78, 7|98, –6|24, 4|44, и 11 | (–33).
б. Отображение неделимости 13†27, 7†50, – 6†23, 4†41, и 11†(–32).
Следующие несколько свойств теории
Свойство 1: если a|1, то a=±1.
Свойство 2: если a|b и b|a, то a=±b
Свойство 3: если a|b и b|c, то a|c
Свойство 4: если a|b и a|c, то a|(m x b + n x c), где m и n — произвольные целые числа.
Пример 2.6
а. Если 3|15 и 15|45 то, согласно третьему свойству, 3|45.
б. Если 3|15 и 3|9, то, согласно четвертому свойству, $$3|(15 \times 2 + 9 \times 4)$$, что означает 3|66.
Положительное целое число может иметь больше чем один делитель. Например, целое число 32 имеет шесть делителей: 1, 2, 4, 8, 16 и 32. Мы можем упомянуть два интересных свойства делителей положительных целых чисел.
Свойство 1: целое число 1 имеет только один делитель — само себя.
Свойство 2: любое положительное целое число имеет по крайней мере два делителя — 1 и само себя (но может иметь больше).
Одно целое число, часто необходимое в криптографии, — наибольший общий делитель двух положительных целых чисел. Два положительных целых числа могут иметь много общих делителей, но только один наибольший общий делитель. Например, общие делители чисел 12 и 140 есть 1, 2 и 4. Однако наибольший общий делитель — 4 (см. рис. 2.6).
(рис 2.6) Общие делители двух целых чиселНахождение наибольшего общего делителя (НОД) двух положительных целых чисел путем составления списка всех общих делителей непригодно для достаточно больших чисел.
К счастью, больше чем 2000 лет назад математик по имени Эвклид разработал алгоритм, который может найти наибольший общий делитель двух положительных целых чисел. Алгоритм Евклида основан на следующих двух фактах (доказательство см. в приложении Q):
Факт 1: НОД (a, 0) = a
Факт 2: НОД (a, b) = НОД (b, r), где r — остаток от деления a на b
Первый факт говорит, что если второе целое число — 0, наибольший общий делитель равен первому числу. Второй факт позволяет нам изменять значение a на b, пока b не станет 0. Например, вычисляя НОД (36, 10), мы можем использовать второй факт несколько раз и один раз первый факт, как показано ниже.
НОД(36,10) = НОД(10,6) = НОД(6,4) = НОД(4,2) = НОД(2,0)
Другими словами, НОД (36, 10) = 2, НОД (10, 6) = 2, и так далее. Это означает, что вместо вычисления НОД (36, 10) мы можем найти НОД (2, 0). Рисунок 2.7 показывает, как мы используем вышеупомянутые два факта, чтобы вычислить НОД (a, b).
(рис 2.7) Алгоритм ЕвклидаДля определения НОД мы используем две переменные, r1 и r2, чтобы запоминать изменяющиеся значения в течение всего процесса. Они имеют начальное значение a и b. На каждом шаге мы вычисляем остаток от деления r1 на r2 и храним результат в виде переменной r. Потом заменяем r1, на r2 и r2 на r и продолжаем шаги, пока r не станет равным 0. В этот момент процесс останавливается и НОД (a, b) равен r1.
Пример 2.7
Нужно найти наибольший общий делитель 2740 и 1760.
Решение
Применим вышеупомянутую процедуру, используя таблицу. Мы присваиваем начальное значение r1 2740 и r2 значение 1760. В таблице
также показаны значения q на каждом шаге. Мы имеем НОД (2740, 1760) = 20.
| q | r1 | r2 | r |
|---|---|---|---|
| 1 | 2740 | 1760 | 980 |
| 1 | 1760 | 980 | 780 |
| 1 | 980 | 780 | 200 |
| 3 | 780 | 200 | 180 |
| 1 | 200 | 180 | 20 |
| 9 | 180 | 20 | 0 |
| 20 | 0 |
Пример 2.8
Найти наибольший общий делитель 25 и 60.
Решение
Мы выбрали этот конкретный пример, чтобы показать, что для алгоритма Евклида безразлично, если первое число меньше, чем второе. Все равно мы получаем правильный ответ НОД (25, 60) = 5.
| q | r1 | r2 | R |
|---|---|---|---|
| 0 | 25 | 60 | 25 |
| 2 | 60 | 25 | 10 |
| 2 | 25 | 10 | 5 |
| 2 | 10 | 5 | 0 |
| 5 | 0 |
Даны два целых числа a и b. Нам зачастую надо найти другие два целых числа, s и t, такие, которые
s x a + t x b = НОД(a,b)
Расширенный алгоритм Евклида может вычислить НОД (a, b) и в то же самое время вычислить значения s и t. Алгоритм и процесс такого вычисления показан на рис. 2.8.
Здесь расширенный r, s и t.
(рис 2.8) Расширенный алгоритм ЕвклидаНа каждом шаге переменные r1, r2 и r используются так же, как в алгоритме Евклида. Переменным r1 и r2 присваиваются начальные значения a и b соответственно. Переменным s1 и s2 присваиваются начальные значения 1 и 0 соответственно. Переменным t1 и t2 присваиваются начальные значения 0 и 1, соответственно. Вычисления r, s и t одинаковы, но с одним отличием. Хотя r — остаток от деления r1 на r2, такого соответствия в других двух группах вычислений нет. Есть только одно частное, q, которое вычисляется как r1/r2 и используется для других двух вычислений.
Пример 2.9
Дано a = 161 и b = 28, надо найти НОД (a, b) и значения s и t.
Решение
r = r1 – q x r2 s = s1 – qs2 t = t1 – q x t2
Для отображения алгоритма мы используем следующую таблицу:
| q | r1 | r2 | R | s1 | s2 | s | t1 | t2 | t |
|---|---|---|---|---|---|---|---|---|---|
| 5 | 161 | 28 | 21 | 1 | 0 | 1 | 0 | 1 | -5 |
| 1 | 28 | 21 | 7 | 0 | 1 | -1 | 1 | -5 | 6 |
| 3 | 21 | 7 | 0 | 1 | -1 | 4 | -5 | 6 | -23 |
| 7 | 0 | -1 | 4 | 6 | -23 |
Мы получаем НОД (161, 28) = 7, s = –1 и t = 6. Ответы могут быть проверены, как это показано ниже.
(–1) x 161 + 6 x 28 = 7
Пример 2.10
Дано a = 17 и b = 0, найти НОД (a, b) и значения s и t.
Решение
Для отображения алгоритма мы используем таблицу.
| q | r1 | r2 | R | s1 | s2 | s | t1 | t2 | t |
|---|---|---|---|---|---|---|---|---|---|
| 17 | 0 | 1 | 0 | 0 | 1 |
Обратите внимание, что нам не надо вычислять q, r и s. Первое значение r2 соответствует условию завершения алгоритма. Мы получаем НОД (17, 0) = 17, s = 1 и t = 0. Это показывает, почему мы должны придавать начальные значения s1 — 1 и t1 — 0. Ответы могут быть проверены так, как это показано ниже:
(1 x 17) + (0 x 0) = 17
Пример 2.11
Даны a = 0 и b = 45, найти НОД (a, b) и значения s и t.
Решение
Для отображения алгоритма мы используем следующую таблицу:
| q | r1 | r2 | R | s1 | s2 | s | t1 | t2 | t |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 45 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 45 | 0 | 0 | 1 | 0 | 1 |
Мы получаем НОД (0,45) = 45, s = 0 и t = 1. Отсюда ясно, что мы должны инициализировать s2 равным 0, а t2 — равным 1. Ответ может быть проверен, как это показано ниже:
(0 x 0) + (1 x 45) = 45
Хотя очень важное приложение расширенного алгоритма Евклида будет рассмотрено далее, здесь мы остановимся на другом приложении — "нахождение решения линейных диофантовых уравнений двух переменных", а именно, уравнения ax + by = c. Мы должны найти значения целых чисел для x и y, которые удовлетворяют этому уравнению. Этот тип уравнения либо не имеет решений, либо имеет бесконечное число решений. Пусть d = НОД (a, b). Если d†c, то уравнение не имеет решения. Если d|c, то мы имеем бесконечное число решений. Одно из них называется частным, остальные — общими.
Если d|c, то можно найти
a1x + b1y = c1, разделив обе части уравнения на d. Это возможно, потому, что d делит a, b, и c в соответствии с предположением.s и t в равенстве a1s + b1t = 1, используя расширенный X0 = (c/d)s и y0 = (c/d)tПосле нахождения
x = x0 + k(b/d) и y = y0 – k(a/d), где k — целое числоПример 2.12
Найти частные и общие решения уравнения 21x + 14y = 35.
Решение
Мы имеем d = НОД (21, 14) = 7. При 7|35 уравнение имеет бесконечное число решений. Мы можем разделить обе стороны уравнения на 7 и получим уравнение 3x + 2y = 5. Используя расширенный s и t, такие, что 3s + 2t = 1. Мы имеем S = 1 и t = –1. Решения будут следующие:
Частное решение : x0 = 5 x 1=5 и y0 = 5 x (–1) = -5 тогда 35/7 =5 Общие: x = 5+ k x 2 y= –5 – k x 3 где k — целое
Поэтому решения будут следующие (5, –5), (7, –8), (9, –11)...
Мы можем легко проверить, что каждое из этих решений удовлетворяет первоначальному уравнению.
Пример 2.13
Рассмотрим очень интересное приложение решения диофантовых уравнений в реальной жизни. Мы хотим найти различные комбинации объектов, имеющих различные значения. Например, мы хотим обменять денежный чек 100$ на некоторое число банкнот 20$ и несколько банкнот по 5$. Имеется много вариантов, которые мы можем найти, решая соответствующее диофантово уравнение 20x + 5y = 100. Обозначим d = НОД (20, 5) = 5 и 5|100. Уравнение имеет бесконечное число решений, но в этом случае приемлемы только несколько из них (только те ответы, в которых и x и y являются неотрицательными целыми числами). Мы делим обе части уравнения на 5, чтобы получить 4x + y = 20, и решаем уравнение 4s + t = 1. Мы можем найти s = 0 и t = 1, используя расширенный алгоритм Эвклида. x и y — (0, 20), (1, 16), (2, 12), (3, 8), (4, 4), (5, 0). Остальная часть решений неприемлема, потому что y становится отрицательным. Кассир в банке должен спросить, какую из вышеупомянутых комбинаций мы хотим. Первое число в скобках обозначает число банкнот по 20$ ; второе число обозначает число банкнот по 5$.
Уравнение деления ( $$a = q \times n + r$$ ), рассмотренное в предыдущей секции, имеет два входа ( a и n ) и два выхода ( q и r ). В модульной арифметике мы интересуемся только одним из выходов — остатком r. Мы не заботимся о частном q. Другими словами, когда мы делим a на n, мы интересуемся только тем, что значение остатка равно r. Это подразумевает, что мы можем представить изображение вышеупомянутого уравнения как a и n и одним выходом r.
Вышеупомянутый mod. Второй вход ( n ) назван модулем. Вывод r назван вычетом. Рисунок 2.9 показывает отношение деления по сравнению с оператором по модулю.
(рис 2.9) Соотношение уравнения деления и оператора по модулю Как показано на рис. 2.9, оператор по модулю ( mod ) выбирает целое число ( a ) из множества Z и положительный модуль ( n ). Оператор определяет неотрицательный остаток ( r ).
Мы можем сказать, что
a mod n = rПример 2.14
Найти результат следующих операций:
a. 27 mod 5
b. 36 mod 12
c. –18 mod 14
d. –7 mod 10
Решение
Мы ищем вычет r. Мы можем разделить a на n и найти q и r. Далее можно игнорировать q и сохранить r.
а. Разделим 27 на 5 - результат: r = 2. Это означает, что 27 mod 5 = 2.
б. Разделим 36 на 12 — результат: r = 0. Это означает, что 36 mod 12 = 0.
в. Разделим (–18) на 14 — результат: r = –4. Однако мы должны прибавить модуль (14), чтобы сделать остаток неотрицательным. Мы имеем r = –4 + 14 = 10. Это означает, что –18 mod 14 = 10.
г. Разделим (–7) на 10 — результат: r = –7. После добавления модуля –7 мы имеем r = 3. Это означает, что –7 mod 10 = 3.
Результат операции по модулю n — всегда целое число между 0 и n - 1. Другими словами, результат a mod n — всегда неотрицательное целое число, меньшее, чем n. Мы можем сказать, что операция по модулю создает набор, который в модульной арифметике можно понимать как систему наименьших вычетов по модулю n, или Zn. Однако мы должны помнить, что хотя существует только одно множество целых чисел ( Z ), мы имеем бесконечное число множеств вычетов ( Zn ), но лишь одно для каждого значения n. Рисунок 2.10 показывает множество Zn и три множества Z2, Z6 и Z11.
(рис 2.10) Некоторые наборы Zn
В криптографии мы часто используем понятие сравнения вместо равенства. Отображение Z в Zn не отображаются "один в один". Бесконечные элементы множества Z могут быть отображены одним элементом Zn. Например, результат 2 mod 10 = 2, 12 mod 10 = 2, 22 mod 10 = 2, и так далее. В модульной арифметике целые числа, подобные 2, 12, и 22, называются сравнимыми по модулю 10 (mod 10). Для того чтобы указать, что два целых числа сравнимы, мы используем оператор сравнения ( $$\equiv $$ ). Мы добавляем mod n к правой стороне сравнения, чтобы определить значение модуля и сделать равенство правильным. Например, мы пишем:
Рисунок 2.11 показывает принцип сравнения. Мы должны объяснить несколько положений.
a. Оператор сравнения напоминает оператор равенства, но между ними есть различия. Первое: оператор равенства отображает элемент Z самого на себя; оператор сравнения отображает элемент Z на элемент Zn. Второе: оператор равенства показывает, что наборы слева и справа соответствуют друг другу "один в один", оператор сравнения — "многие — одному".
(рис 2.11) Принцип сравнения б. Обозначение ( mod n ), которое мы вставляем с правой стороны оператора сравнения, обозначает признак множества ( Zn ). Мы должны добавить это обозначение, чтобы показать, какой модуль используется в отображении. Символ, используемый здесь, не имеет того же самого значения, как бинарный оператор в уравнении деления. Другими словами, символ mod в выражении 12 mod 10 — оператор; а сочетание ( mod 10 ) в сравнении $$2 \equiv 12(\bmod 10)$$ означает, что набор — Z10.
Система вычетов [a], или [a]n, — множество целых чисел, сравнимых по модулю n. Другими словами, это набор всех целых чисел, таких, что x = a (mod n). Например, если n = 5, мы имеем множество из пяти элементов [0], [1], [2], [3] и [4], таких как это показано ниже:
[0] = {…., –15, -10, –5, 0, 5, 10, 15, …}
[1] = {…., –14, –9, –4, 1, 6 , 11, 16,…}
[2] = {…., –13, –8, –3, 2, 7, 12, 17,…}
[3] = {...., –12, –7, –2, 3, 8, 13, 18,…}
[4] = {…., –11, –6, –1, 4, 9, 14, 19,…}
Целые числа в наборе [0] все дают остаток 0 при делении на 5 (сравнимы по модулю 5 ). Целые числа в наборе [1] все дают остаток 1 при делении на 5 (сравнимы по модулю 5 ), и так далее. В каждом наборе есть один элемент, называемый наименьшим (неотрицательным) вычетом. В наборе [0] это элемент 0 ; в наборе [1] — 1, и так далее. Набор, который показывает все наименьшие вычеты: Z5 = {0, 1, 2, 3, 4}. Другими словами, набор Zn — набор всех наименьших вычетов по модулю n.
Понятие "сравнение" может быть лучше раскрыто при использовании круга в качестве модели. Так же, как мы применяем линию, чтобы показать распределение целых чисел в Z, мы можем использовать круг, чтобы показать распределение целых чисел в Zn.
(рис 2.12) Сравнение использования диаграмм для Z и Zn Рисунок 2.12 позволяет сравнить два этих подхода. Целые числа от 0 до n–1 расположены равномерно вокруг круга. Все целые числа, сравнимые по модулю n, занимают одни и те же точки в круге. Положительные и отрицательные целые числа от Z отображаются в круге одним и тем же способом, соблюдая симметрию между ними.
Пример 2.15
Мы пользуемся сравнением по модулю в нашей ежедневной жизни; например, мы применяем часы, чтобы измерить время. Наша система часов использует арифметику по модулю 12. Однако вместо 0 мы берем отсечку 12, так что наша система часов начинается с 0 (или 12 ) и идет до 11. Поскольку наши сутки длятся 24 часа, мы считаем по кругу два раза и обозначаем первое вращение как утро до полудня, а второе — как вечер после полудня.
Три Z, могут также быть определены для набора Zn. Результат, возможно, должен быть отображен в Zn с использованием операции по модулю, как это показано на рис. 2.13.
(рис 2.13) Бинарные операции в Zn Фактически применяются два набора операторов: первый набор — один из a и b ) могут быть членами Z или Zn.
Пример 2.16
Выполните следующие операторы (поступающие от Zn ):
а. Сложение 7 и 14 в Z15
б. Вычитание 11 из 7 в Z13
в. Умножение 11 на 7 в Z20
Решение
Ниже показаны два шага для каждой операции:
(14+7) mod 15 -> (21) mod 15 = 6 (7–11) mod 13 -> (-4) mod 13 = 9 (7x11) mod 20 -> (77) mod 20 = 17
Пример 2.17
Выполните следующие операции (поступающие от Zn ):
a. Сложение 17 и 27 в Z14
b. Вычитание 43 из 12 в Z13
c. Умножение 123 на -10 в Z19
Решение
Ниже показаны два шага для каждой операции:
(17 + 27) mod 14 -> (44) mod 14 = 2 (12 – 43) mod 13 -> (–31) mod 13 = 8 ((123) x (–10)) mod 19 -> (–1230) mod 19 = 5
Мы уже упоминали, что два входа для трех Z или Zn. Следующие свойства позволяют нам сначала отображать два входа к Zn (если они прибывают от Z ) перед выполнением этих трех
(рис 2.14) Свойства оператора mod
Первое свойство: (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 x b) mod n = [(a mod n) x (b mod n)] mod n
Рисунок 2.14 показывает процесс до и после применения указанных выше свойств. Хотя по рисунку видно, что процесс с применением этих свойств более длинен, мы должны помнить, что в криптографии мы имеем дело с очень большими целыми числами. Например, если мы умножаем очень большое целое число на другое очень большое целое число, которое настолько большое, что не может быть записано в компьютере, то применение вышеупомянутых свойств позволяет уменьшить первые два операнда прежде, чем начать умножение. Другими словами, перечисленные свойства позволяют нам работать с меньшими числами. Этот факт станет понятнее при обсуждении экспоненциальных операций в последующих лекциях.
Пример 2.18
Следующие примеры показывают приложение вышеупомянутых свойств.
Пример 2.19
В арифметике мы часто должны находить остаток от степеней числа 10 при делении на целое число. Например, мы должны найти 10 mod 3, 102 mod 3, 103 mod 3, и так далее. Мы также должны найти 10 mod 7, 102 mod 7, 103 mod 7, и так далее. Третье свойство модульных операторов, упомянутое выше, делает жизнь намного проще.
10n mod x = (10 mod x)n Применение третьего свойства n раз.
Мы имеем
10 mod 3 = 1 -> 10n mod 3 = (10 mod 3)n = 1 10 mod 9 = 1 -> 10n mod 9 = (10 mod 9)n = 1 10 mod 7 = 3 -> 10n mod 7 = (10 mod 7)n = 3n mod 7
Пример 2.20
Мы уже говорили, что в арифметике остаток от целого числа, разделенного на 3, такой же, как остаток от деления суммы его десятичных цифр. Другими словами, остаток от деления 6371 равен остатку от деления суммы его цифр (17), на 3. Мы можем доказать, что это утверждение использует свойства модульного оператора. Запишем целое число как сумму его цифр, умноженных на степени 10.
a = an10n +………+ a1101 + a0100 Например: 6371 = 6 x 103 + 3 x 102+ 7 x 101+ 1 x 100
Теперь мы можем применить модульную операцию к двум сторонам равенства и использовать результат предыдущего примера, где остаток 10n mod 3 равен 1.
a mod 3 = (an x 10n +…+ a1 x 101+ a0 x 100) mod 3 = (an x 10n) mod 3 +…+ (a1 x 101) mod 3 + (a0 x 100 mod 3) mod 3 = (an mod 3) x (10n mod 3) +…+ (a1 mod 3) x (101 mod 3) + (a0 mod 3) x (100 mod 3) mod 3 = ((an mod 3) +…+ (a1 mod 3) + (a0 mod 3)) mod 3 = (an +…+ a1 + a0) mod 3
Когда мы работаем в модульной арифметике, нам часто нужно найти операцию, которая позволяет вычислить величину, обратную заданному числу. Мы обычно ищем аддитивную инверсию (оператор, обратный сложению) или мультипликативную инверсию (оператор, обратный умножению).
В Zn два числа a и b аддитивно инверсны друг другу, если b = n – a. Например,
В Zn аддитивная инверсия числу a может быть вычислена как b = n – a. Например, аддитивная инверсия 4 в Z10 равна 10 – 4 = 6.
Обратите внимание, что в модульной арифметике каждое число имеет аддитивную инверсию, и эта инверсия уникальна; каждое число имеет одну и только одну аддитивную инверсию. Однако инверсия числа может быть непосредственно тем же самым числом.
Пример 2.21
Найдите все взаимно обратные пары по сложению в Z10.
Решение
Даны шесть пар аддитивных инверсий — (0, 0), (1, 9), (2, 8), (3, 7), (4, 6) и (5, 5). В этом списке 0 — инверсия самому себе; так же и 5. Обратите внимание: аддитивные инверсии обратны друг другу; если 4 — аддитивная инверсия 6, тогда 6 — также аддитивная инверсия числу 4.
В Zn два числа a и b мультипликативно инверсны друг другу, если
Например, если модуль равен 10, то мультипликативная инверсия 3 есть 7. Другими словами, мы имеем $$(3 \times 7)\bmod 10 \equiv 1$$.
Может быть доказано, что a имеет мультипликативную инверсию в Zn, если только НОД(n, a) = 1. В этом случае говорят, что a и n взаимно простые.
Пример 2.22
Найти мультипликативную инверсию 8 в Z10.
Решение
Мультипликативная инверсия не существует, потому что $$HOD\left( {{\text{1}}0,{\text{8}}} \right) = {\text{2}} \ne {\text{1}}$$. Другими словами, мы не можем найти число между 0 и 9, такое, что при умножении на 8 результат сравним с 1 по mod 10.
Пример 2.23
Найти все мультипликативные инверсии в Z10.
Решение
Есть только три пары, удовлетворяющие условиям существования мультипликативной инверсии: (1, 1), (3, 7) и (9, 9). Числа 0, 2, 4, 5, 6 и 8 не имеют мультипликативной инверсии.
Мы можем проверить, что
(1 x 1) mod 10 = 1 (3 x 7) mod 10 = 1 (9 x 9) mod 10 = 1
Пример 2.24
Найти все мультипликативные обратные пары в Z11.
Решение
Мы имеем следующие пары: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8) и (10, 10). При переходе от Z10 к Z11 число пар увеличивается. При Z11 НОД (11, a) = 1 (взаимно простые) для всех значений a, кроме 0. Это означает, что все целые числа от 1 до 10 имеют мультипликативные инверсии.
a в Zn имеет мультипликативную инверсию тогда и только тогда, если НОД (n, a) = 1(mod n)Расширенный b в Zn, когда даны n и b и инверсия существует. Для этого нам надо заменить первое целое число a на n (модуль). Далее мы можем утверждать, что алгоритм может найти s и t, такие, что $$s \times n + b \times t = HOD\left( {n,b} \right)$$. Однако если мультипликативная инверсия b существует, НОД (n, b) должен быть 1. Так что уравнение будет иметь вид
Теперь мы применяем операции по модулю к обеим сторонам уравнения. Другими словами, мы отображаем каждую сторону к Zn. Тогда мы будем иметь
(s x n + b x t) mod n =1 mod n [(s x n) mod n] + [(b x t) mod n] = 1 mod n 0 + [(b x t) mod n ] = 1 (b x t) mod n =1 -> Это означает, что t – это мультипликативная инверсия b в Zn
Обратите внимание, что $$[(s \times n)\bmod n]$$ на третьей строке — 0, потому что, если мы делим $$(s \times n)n$$, частное — s, а остаток — 0.
b в Zn , когда даны n и b и НОД (n, b) = 1 .
Мультипликативная инверсия .Рисунок 2.15 показывает, как мы находим мультипликативную инверсию числа, используя расширенный
(рис 2.15) Применение расширенного алгоритма Евклида для поиска мультипликативной инверсииПример 2.25
Найти мультипликативную инверсию 11 в Z26.
Решение
Мы используем таблицу, аналогичную одной из тех, которые мы уже применяли прежде при данных r1 = 26 и r2 = 11. Нас интересует только значение t.
| q | r1 | r2 | r | t1 | t2 | t |
|---|---|---|---|---|---|---|
| 2 | 26 | 11 | 4 | 0 | 1 | -2 |
| 2 | 11 | 4 | 3 | 1 | -2 | 5 |
| 1 | 4 | 3 | 1 | -2 | 5 | -7 |
| 3 | 3 | 1 | 0 | 5 | -7 | 26 |
| 1 | 0 | -7 | 26 |
НОД (26, 11) = 1, что означает, что мультипликативная инверсия 11 существует. Расширенный t1 = (–7).
Мультипликативная инверсия равна (–7) mod 26 = 19. Другими словами, 11 и 19 — мультипликативная инверсия в Z26. Мы можем видеть, что $$(11 \times 19)\bmod 26 = 209\bmod 26 = 1$$.
Пример 2.26
Найти мультипликативную инверсию 23 в Z100.
Решение
Мы используем таблицу, подобную той, которую применяли до этого при r1 = 100 и r2 = 23. Нас интересует только значение t.
| q | r1 | r2 | r | t1 | t2 | t |
|---|---|---|---|---|---|---|
| 4 | 100 | 23 | 8 | 0 | 1 | -4 |
| 2 | 23 | 8 | 7 | 1 | -4 | 19 |
| 1 | 8 | 7 | 1 | -4 | 9 | -13 |
| 7 | 7 | 1 | 0 | 9 | -13 | 100 |
| 1 | 0 | -13 | 100 |
НОД (100, 23) = 1, что означает, что инверсия 23 существует. Расширенный Евклидов алгоритм дает t1 =-13. Инверсия — (–13) mod 100 = 87. Другими словами, 13 и 87 — мультипликативные инверсии в Z100. Мы можем видеть, что $$(23 \times 87)\bmod 100 = 2001\bmod 100 = 1$$.
Пример 2.27
Найти мультипликативную инверсию 12 в Z26.
Решение
Мы используем таблицу, подобную той, которую мы применяли раньше при r1 = 26 и r2 = 12.
| q | r1 | r2 | r | t1 | t2 | t |
|---|---|---|---|---|---|---|
| 2 | 26 | 12 | 2 | 0 | 1 | |
| 6 | 12 | 2 | 0 | 1 | -2 | |
| 2 | 0 | -2 | 13 |
$$HOD\left( {{\text{26}},{\text{12}}} \right) = {\text{2}} \ne {\text{1}}$$, что означает отсутвствие для числа 12 мультипликативной инверсии в Z26
Рисунок 2.16 показывает две таблицы для сложения и умножения. При сложении таблиц каждое целое число имеет аддитивную инверсию. Обратные пары могут быть найдены, если результат их сложения — ноль. Мы имеем (0, 0), (1, 9), (2, 8), (3, 7), (4, 6) и (5, 5). При умножении таблиц мы получаем только три мультипликативных пары (1, 1), (3, 7) и (9, 9). Пары могут быть найдены, когда результат умножения равен 1. Обе таблицы симметричны по диагонали, от левой вершины к нижней вершине справа. При этом можно обнаружить свойства коммутативности для сложения и умножения ( a+b = b+a и $$a \times b = b \times a$$ ). Таблица сложения также показывает, что каждый ряд или колонка может поменяться с другим рядом или колонкой. Для таблицы умножения это неверно.
(рис 2.16) Таблицы сложения и умножения для Z10
В криптографии мы часто работаем с инверсиями. Если отправитель посылает целое число (например, ключ для шифрования слова), приемник применяет инверсию этого целого числа (например, ключ декодирования). Если это действие (алгоритм шифрования/декодирования) является сложением, множество Zn может быть использовано как множество возможных ключей, потому что каждое целое число в этом множестве имеет аддитивную инверсию. С другой стороны, если действие (алгоритм шифрования/декодирования) — умножение, Zn не может быть множеством возможных ключей, потому что только некоторые члены этого множества имеют мультипликативную инверсию. Нам нужно другое множество, которое является подмножеством Zn и включает в себя только целые числа, и при этом в Zn они имеют уникальную мультипликативную инверсию. Это множество обозначается Zn*. Рисунок 2.17 показывает некоторые
случаи двух множеств. Обратите внимание, что множество Zn*
может быть получено из таблицы умножения типа показанной на рис. 2.16.
Каждый член Zn имеет аддитивную инверсию, но только некоторые члены имеют мультипликативную инверсию. Каждый член Zn* имеет мультипликативную инверсию, но только некоторые члены множества имеют аддитивную инверсию.
Zn , когда необходимы аддитивные инверсии; мы должны использовать Zn* , когда необходимы мультипликативные инверсии.
(рис 2.17) Некоторые множества Zn и Zn*
Криптография часто использует еще два множества: Zp, и Zp*. Модули в этих двух множествах — простые числа. Простые числа будут обсуждаться в следующих лекциях; пока можно сказать, что простое число имеет только два делителя: целое число 1 и само себя.
Множество Zp — то же самое, что и Zn, за исключением того, что n — простое число. Zp содержит все целые числа от 0 до p – 1. Каждый элемент в Zp имеет аддитивную инверсию; каждый элемент кроме 0 имеет мультипликативную инверсию.
Множество Zp* — то же самое, что Zn*, за исключением того, что Zp* содержит все целые числа от 1 до p – 1. Каждый элемент в Zp имеет аддитивную и мультипликативную инверсии. Zp* очень хороший кандидат, когда мы нуждаемся во множестве, которое поддерживает аддитивную и мультипликативную инверсии.
Ниже показаны два множества, когда p = 13.
Z13 = {0,1,2,3,4,5,6,7,8,9,10,11,12},
Z13* = {1,2,3,4,5,6,7,8,9,10,11,12},
Криптография базируется на некоторых специфических областях математики, включая теорию чисел, линейную алгебру и алгебраические структуры. В этой лекции мы обсуждаем только те темы в вышеупомянутых областях, которые необходимы для понимания содержания следующих нескольких лекций. Читатели, которые знакомы с этими темами, могут пропустить лекцию полностью или частично. Подобные теоретические лекции встречаются всюду в этом курсе, когда это необходимо.
В арифметике целых чисел мы используем множество целых чисел и несколько операций. Вы знакомы с этим множеством и соответствующими операциями, но они рассмотрены здесь, чтобы объяснить потом основы действий со сравнениями по модулю m.
Множество целых чисел, обозначенных Z, содержит все числа (без дробей) от минус бесконечности до плюс бесконечности (рис. 2.1).
(рис 2.1) Множество целых чисел
В криптографии нас интересует три a и b ) и выход ( c ), как это показано на рис. 2.2. Два входа принимают числа из множества целых чисел; выход выводит результат операции — число из множества целых чисел.
Обращаем внимание, что деление не относится к этой категории операций, потому что мы скоро убедимся, что этой операции нужны два выхода вместо одного.
(рис 2.2) Три бинарных операции для множества целых чиселПример 2.1
Следующие примеры показывают результаты трех бинарных операций на множестве двух целых чисел. Поскольку каждый вход может быть или положителен или отрицателен, мы имеем четыре случая для каждой операции.
Сложение 5+9=14 (-5)+9=4 5+(-9)=-4 (-5)+(-9)=-14 Вычитание 5-9=-4 (-5)-9=-14 5 - (-9)=14 (-5)- (-9)=+4 Умножение 5 x 9=45 (-5) x 9=-45 5 x (-9)=-45 (-5) x (-9)=45
В арифметике целых чисел, если мы a делим на n, мы можем получить q и r. Отношения между этими четырьмя целыми числами можно показать как
В этом равенстве a называется делимое ; q — частное ; n — делитель и r — остаток. Обратите внимание, что это — не операция, поскольку результат деления a на n — это два целых числа, q и r. Мы будем называть это уравнением деления.
Пример 2.2
Предположим, что a = 255, а n = 23. Мы можем найти q = 11 и r = 2, используя алгоритм деления, мы знаем из элементарной арифметики — оно определяется, как показано на рис. 2.3.
(рис 2.3) Пример 2.2, нахождение частного и остаткаБольшинство компьютерных языков может найти частное и остаток, используя заданные языком операторы. Например, на языке C оператор "/" может найти частное, а оператор "%" — остаток.
Когда мы используем вышеупомянутое уравнение деления в криптографии, мы налагаем два ограничения. Первое требование: чтобы делитель был положительным целым числом ( n > 0 ). Второе требование: чтобы остаток был неотрицательным целым числом ( r >= 0 ). Рисунок 2.4 показывает эти требования с двумя указанными ограничениями.
(рис 2.4) Алгоритм деления целых чиселПример 2.3
Предположим, мы используем компьютер или калькулятор, а r и q отрицательны, при отрицательном a. Как можно сделать, чтобы выполнялось ограничение, что число r должно быть положительным? Решение простое: мы уменьшаем значение q на 1 и добавляем значение n к r, чтобы r стало положительным.
Мы уменьшили ( –23 ), получили ( –24 ) и добавили 11 к ( –2 ), чтобы получить + 9. Полученное равенство эквивалентно исходному.
Мы можем изобразить рассмотренные выше уравнения с двумя ограничениями на n и r на рис. 2.5 с помощью двух графов. Первый показывает случай, когда число a положительно; второй — когда отрицательно.
(рис 2.5) Граф алгоритма деленияГраф начинается с нуля и показывает, как мы можем достигнуть точки, представляющей целое число a на линии. В случае положительного a мы должны перемещаться на величину $$q \times n$$ направо и затем добавить дополнительную величину r в том же самом направлении. В случае отрицательного a мы должны двигаться на величину $$(q - 1) \times n$$ налево (число q в этом случае отрицательно) и затем дополнять число r в противоположном для указанного выше движения направлении. В обоих случаях значение r положительно.
Теперь кратко обсудим теорию делимости — тема, с которой мы часто сталкиваемся в криптографии. Если a не равно нулю, а r = 0, в равенстве деления мы имеем
a = q x nМы тогда говорим, что a делится на n (или n — делитель a ). Мы можем также сказать, что a делится без остатка на n. Когда мы не интересуемся значением q, мы можем записать вышеупомянутые отношения как n|a. Если остаток не является нулевым, то n не делит, и мы можем записать отношения как n†a.
Пример 2.4
a. Целое число 4 делит целое число 32, потому что $$32=8 \times 4$$. Это можно отобразить как 4|32. Число 8 не делит число 42, потому что $$42 = 5 \times 8 + 2$$. В этом уравнении число 2 — остаток. Это можно отобразить как 8†42.
Пример 2.5
а. Отображение 13|78, 7|98, –6|24, 4|44, и 11 | (–33).
б. Отображение неделимости 13†27, 7†50, – 6†23, 4†41, и 11†(–32).
Следующие несколько свойств теории
Свойство 1: если a|1, то a=±1.
Свойство 2: если a|b и b|a, то a=±b
Свойство 3: если a|b и b|c, то a|c
Свойство 4: если a|b и a|c, то a|(m x b + n x c), где m и n — произвольные целые числа.
Пример 2.6
а. Если 3|15 и 15|45 то, согласно третьему свойству, 3|45.
б. Если 3|15 и 3|9, то, согласно четвертому свойству, $$3|(15 \times 2 + 9 \times 4)$$, что означает 3|66.
Положительное целое число может иметь больше чем один делитель. Например, целое число 32 имеет шесть делителей: 1, 2, 4, 8, 16 и 32. Мы можем упомянуть два интересных свойства делителей положительных целых чисел.
Свойство 1: целое число 1 имеет только один делитель — само себя.
Свойство 2: любое положительное целое число имеет по крайней мере два делителя — 1 и само себя (но может иметь больше).
Одно целое число, часто необходимое в криптографии, — наибольший общий делитель двух положительных целых чисел. Два положительных целых числа могут иметь много общих делителей, но только один наибольший общий делитель. Например, общие делители чисел 12 и 140 есть 1, 2 и 4. Однако наибольший общий делитель — 4 (см. рис. 2.6).
(рис 2.6) Общие делители двух целых чиселНахождение наибольшего общего делителя (НОД) двух положительных целых чисел путем составления списка всех общих делителей непригодно для достаточно больших чисел.
К счастью, больше чем 2000 лет назад математик по имени Эвклид разработал алгоритм, который может найти наибольший общий делитель двух положительных целых чисел. Алгоритм Евклида основан на следующих двух фактах (доказательство см. в приложении Q):
Факт 1: НОД (a, 0) = a
Факт 2: НОД (a, b) = НОД (b, r), где r — остаток от деления a на b
Первый факт говорит, что если второе целое число — 0, наибольший общий делитель равен первому числу. Второй факт позволяет нам изменять значение a на b, пока b не станет 0. Например, вычисляя НОД (36, 10), мы можем использовать второй факт несколько раз и один раз первый факт, как показано ниже.
НОД(36,10) = НОД(10,6) = НОД(6,4) = НОД(4,2) = НОД(2,0)
Другими словами, НОД (36, 10) = 2, НОД (10, 6) = 2, и так далее. Это означает, что вместо вычисления НОД (36, 10) мы можем найти НОД (2, 0). Рисунок 2.7 показывает, как мы используем вышеупомянутые два факта, чтобы вычислить НОД (a, b).
(рис 2.7) Алгоритм ЕвклидаДля определения НОД мы используем две переменные, r1 и r2, чтобы запоминать изменяющиеся значения в течение всего процесса. Они имеют начальное значение a и b. На каждом шаге мы вычисляем остаток от деления r1 на r2 и храним результат в виде переменной r. Потом заменяем r1, на r2 и r2 на r и продолжаем шаги, пока r не станет равным 0. В этот момент процесс останавливается и НОД (a, b) равен r1.
Пример 2.7
Нужно найти наибольший общий делитель 2740 и 1760.
Решение
Применим вышеупомянутую процедуру, используя таблицу. Мы присваиваем начальное значение r1 2740 и r2 значение 1760. В таблице
также показаны значения q на каждом шаге. Мы имеем НОД (2740, 1760) = 20.
| q | r1 | r2 | r |
|---|---|---|---|
| 1 | 2740 | 1760 | 980 |
| 1 | 1760 | 980 | 780 |
| 1 | 980 | 780 | 200 |
| 3 | 780 | 200 | 180 |
| 1 | 200 | 180 | 20 |
| 9 | 180 | 20 | 0 |
| 20 | 0 |
Пример 2.8
Найти наибольший общий делитель 25 и 60.
Решение
Мы выбрали этот конкретный пример, чтобы показать, что для алгоритма Евклида безразлично, если первое число меньше, чем второе. Все равно мы получаем правильный ответ НОД (25, 60) = 5.
| q | r1 | r2 | R |
|---|---|---|---|
| 0 | 25 | 60 | 25 |
| 2 | 60 | 25 | 10 |
| 2 | 25 | 10 | 5 |
| 2 | 10 | 5 | 0 |
| 5 | 0 |
Даны два целых числа a и b. Нам зачастую надо найти другие два целых числа, s и t, такие, которые
s x a + t x b = НОД(a,b)
Расширенный алгоритм Евклида может вычислить НОД (a, b) и в то же самое время вычислить значения s и t. Алгоритм и процесс такого вычисления показан на рис. 2.8.
Здесь расширенный r, s и t.
(рис 2.8) Расширенный алгоритм ЕвклидаНа каждом шаге переменные r1, r2 и r используются так же, как в алгоритме Евклида. Переменным r1 и r2 присваиваются начальные значения a и b соответственно. Переменным s1 и s2 присваиваются начальные значения 1 и 0 соответственно. Переменным t1 и t2 присваиваются начальные значения 0 и 1, соответственно. Вычисления r, s и t одинаковы, но с одним отличием. Хотя r — остаток от деления r1 на r2, такого соответствия в других двух группах вычислений нет. Есть только одно частное, q, которое вычисляется как r1/r2 и используется для других двух вычислений.
Пример 2.9
Дано a = 161 и b = 28, надо найти НОД (a, b) и значения s и t.
Решение
r = r1 – q x r2 s = s1 – qs2 t = t1 – q x t2
Для отображения алгоритма мы используем следующую таблицу:
| q | r1 | r2 | R | s1 | s2 | s | t1 | t2 | t |
|---|---|---|---|---|---|---|---|---|---|
| 5 | 161 | 28 | 21 | 1 | 0 | 1 | 0 | 1 | -5 |
| 1 | 28 | 21 | 7 | 0 | 1 | -1 | 1 | -5 | 6 |
| 3 | 21 | 7 | 0 | 1 | -1 | 4 | -5 | 6 | -23 |
| 7 | 0 | -1 | 4 | 6 | -23 |
Мы получаем НОД (161, 28) = 7, s = –1 и t = 6. Ответы могут быть проверены, как это показано ниже.
(–1) x 161 + 6 x 28 = 7
Пример 2.10
Дано a = 17 и b = 0, найти НОД (a, b) и значения s и t.
Решение
Для отображения алгоритма мы используем таблицу.
| q | r1 | r2 | R | s1 | s2 | s | t1 | t2 | t |
|---|---|---|---|---|---|---|---|---|---|
| 17 | 0 | 1 | 0 | 0 | 1 |
Обратите внимание, что нам не надо вычислять q, r и s. Первое значение r2 соответствует условию завершения алгоритма. Мы получаем НОД (17, 0) = 17, s = 1 и t = 0. Это показывает, почему мы должны придавать начальные значения s1 — 1 и t1 — 0. Ответы могут быть проверены так, как это показано ниже:
(1 x 17) + (0 x 0) = 17
Пример 2.11
Даны a = 0 и b = 45, найти НОД (a, b) и значения s и t.
Решение
Для отображения алгоритма мы используем следующую таблицу:
| q | r1 | r2 | R | s1 | s2 | s | t1 | t2 | t |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 45 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 45 | 0 | 0 | 1 | 0 | 1 |
Мы получаем НОД (0,45) = 45, s = 0 и t = 1. Отсюда ясно, что мы должны инициализировать s2 равным 0, а t2 — равным 1. Ответ может быть проверен, как это показано ниже:
(0 x 0) + (1 x 45) = 45
Хотя очень важное приложение расширенного алгоритма Евклида будет рассмотрено далее, здесь мы остановимся на другом приложении — "нахождение решения линейных диофантовых уравнений двух переменных", а именно, уравнения ax + by = c. Мы должны найти значения целых чисел для x и y, которые удовлетворяют этому уравнению. Этот тип уравнения либо не имеет решений, либо имеет бесконечное число решений. Пусть d = НОД (a, b). Если d†c, то уравнение не имеет решения. Если d|c, то мы имеем бесконечное число решений. Одно из них называется частным, остальные — общими.
Если d|c, то можно найти
a1x + b1y = c1, разделив обе части уравнения на d. Это возможно, потому, что d делит a, b, и c в соответствии с предположением.s и t в равенстве a1s + b1t = 1, используя расширенный X0 = (c/d)s и y0 = (c/d)tПосле нахождения
x = x0 + k(b/d) и y = y0 – k(a/d), где k — целое числоПример 2.12
Найти частные и общие решения уравнения 21x + 14y = 35.
Решение
Мы имеем d = НОД (21, 14) = 7. При 7|35 уравнение имеет бесконечное число решений. Мы можем разделить обе стороны уравнения на 7 и получим уравнение 3x + 2y = 5. Используя расширенный s и t, такие, что 3s + 2t = 1. Мы имеем S = 1 и t = –1. Решения будут следующие:
Частное решение : x0 = 5 x 1=5 и y0 = 5 x (–1) = -5 тогда 35/7 =5 Общие: x = 5+ k x 2 y= –5 – k x 3 где k — целое
Поэтому решения будут следующие (5, –5), (7, –8), (9, –11)...
Мы можем легко проверить, что каждое из этих решений удовлетворяет первоначальному уравнению.
Пример 2.13
Рассмотрим очень интересное приложение решения диофантовых уравнений в реальной жизни. Мы хотим найти различные комбинации объектов, имеющих различные значения. Например, мы хотим обменять денежный чек 100$ на некоторое число банкнот 20$ и несколько банкнот по 5$. Имеется много вариантов, которые мы можем найти, решая соответствующее диофантово уравнение 20x + 5y = 100. Обозначим d = НОД (20, 5) = 5 и 5|100. Уравнение имеет бесконечное число решений, но в этом случае приемлемы только несколько из них (только те ответы, в которых и x и y являются неотрицательными целыми числами). Мы делим обе части уравнения на 5, чтобы получить 4x + y = 20, и решаем уравнение 4s + t = 1. Мы можем найти s = 0 и t = 1, используя расширенный алгоритм Эвклида. x и y — (0, 20), (1, 16), (2, 12), (3, 8), (4, 4), (5, 0). Остальная часть решений неприемлема, потому что y становится отрицательным. Кассир в банке должен спросить, какую из вышеупомянутых комбинаций мы хотим. Первое число в скобках обозначает число банкнот по 20$ ; второе число обозначает число банкнот по 5$.
Уравнение деления ( $$a = q \times n + r$$ ), рассмотренное в предыдущей секции, имеет два входа ( a и n ) и два выхода ( q и r ). В модульной арифметике мы интересуемся только одним из выходов — остатком r. Мы не заботимся о частном q. Другими словами, когда мы делим a на n, мы интересуемся только тем, что значение остатка равно r. Это подразумевает, что мы можем представить изображение вышеупомянутого уравнения как a и n и одним выходом r.
Вышеупомянутый mod. Второй вход ( n ) назван модулем. Вывод r назван вычетом. Рисунок 2.9 показывает отношение деления по сравнению с оператором по модулю.
(рис 2.9) Соотношение уравнения деления и оператора по модулю Как показано на рис. 2.9, оператор по модулю ( mod ) выбирает целое число ( a ) из множества Z и положительный модуль ( n ). Оператор определяет неотрицательный остаток ( r ).
Мы можем сказать, что
a mod n = rПример 2.14
Найти результат следующих операций:
a. 27 mod 5
b. 36 mod 12
c. –18 mod 14
d. –7 mod 10
Решение
Мы ищем вычет r. Мы можем разделить a на n и найти q и r. Далее можно игнорировать q и сохранить r.
а. Разделим 27 на 5 - результат: r = 2. Это означает, что 27 mod 5 = 2.
б. Разделим 36 на 12 — результат: r = 0. Это означает, что 36 mod 12 = 0.
в. Разделим (–18) на 14 — результат: r = –4. Однако мы должны прибавить модуль (14), чтобы сделать остаток неотрицательным. Мы имеем r = –4 + 14 = 10. Это означает, что –18 mod 14 = 10.
г. Разделим (–7) на 10 — результат: r = –7. После добавления модуля –7 мы имеем r = 3. Это означает, что –7 mod 10 = 3.
Результат операции по модулю n — всегда целое число между 0 и n - 1. Другими словами, результат a mod n — всегда неотрицательное целое число, меньшее, чем n. Мы можем сказать, что операция по модулю создает набор, который в модульной арифметике можно понимать как систему наименьших вычетов по модулю n, или Zn. Однако мы должны помнить, что хотя существует только одно множество целых чисел ( Z ), мы имеем бесконечное число множеств вычетов ( Zn ), но лишь одно для каждого значения n. Рисунок 2.10 показывает множество Zn и три множества Z2, Z6 и Z11.
(рис 2.10) Некоторые наборы Zn
В криптографии мы часто используем понятие сравнения вместо равенства. Отображение Z в Zn не отображаются "один в один". Бесконечные элементы множества Z могут быть отображены одним элементом Zn. Например, результат 2 mod 10 = 2, 12 mod 10 = 2, 22 mod 10 = 2, и так далее. В модульной арифметике целые числа, подобные 2, 12, и 22, называются сравнимыми по модулю 10 (mod 10). Для того чтобы указать, что два целых числа сравнимы, мы используем оператор сравнения ( $$\equiv $$ ). Мы добавляем mod n к правой стороне сравнения, чтобы определить значение модуля и сделать равенство правильным. Например, мы пишем:
Рисунок 2.11 показывает принцип сравнения. Мы должны объяснить несколько положений.
a. Оператор сравнения напоминает оператор равенства, но между ними есть различия. Первое: оператор равенства отображает элемент Z самого на себя; оператор сравнения отображает элемент Z на элемент Zn. Второе: оператор равенства показывает, что наборы слева и справа соответствуют друг другу "один в один", оператор сравнения — "многие — одному".
(рис 2.11) Принцип сравнения б. Обозначение ( mod n ), которое мы вставляем с правой стороны оператора сравнения, обозначает признак множества ( Zn ). Мы должны добавить это обозначение, чтобы показать, какой модуль используется в отображении. Символ, используемый здесь, не имеет того же самого значения, как бинарный оператор в уравнении деления. Другими словами, символ mod в выражении 12 mod 10 — оператор; а сочетание ( mod 10 ) в сравнении $$2 \equiv 12(\bmod 10)$$ означает, что набор — Z10.
Система вычетов [a], или [a]n, — множество целых чисел, сравнимых по модулю n. Другими словами, это набор всех целых чисел, таких, что x = a (mod n). Например, если n = 5, мы имеем множество из пяти элементов [0], [1], [2], [3] и [4], таких как это показано ниже:
[0] = {…., –15, -10, –5, 0, 5, 10, 15, …}
[1] = {…., –14, –9, –4, 1, 6 , 11, 16,…}
[2] = {…., –13, –8, –3, 2, 7, 12, 17,…}
[3] = {...., –12, –7, –2, 3, 8, 13, 18,…}
[4] = {…., –11, –6, –1, 4, 9, 14, 19,…}
Целые числа в наборе [0] все дают остаток 0 при делении на 5 (сравнимы по модулю 5 ). Целые числа в наборе [1] все дают остаток 1 при делении на 5 (сравнимы по модулю 5 ), и так далее. В каждом наборе есть один элемент, называемый наименьшим (неотрицательным) вычетом. В наборе [0] это элемент 0 ; в наборе [1] — 1, и так далее. Набор, который показывает все наименьшие вычеты: Z5 = {0, 1, 2, 3, 4}. Другими словами, набор Zn — набор всех наименьших вычетов по модулю n.
Понятие "сравнение" может быть лучше раскрыто при использовании круга в качестве модели. Так же, как мы применяем линию, чтобы показать распределение целых чисел в Z, мы можем использовать круг, чтобы показать распределение целых чисел в Zn.
(рис 2.12) Сравнение использования диаграмм для Z и Zn Рисунок 2.12 позволяет сравнить два этих подхода. Целые числа от 0 до n–1 расположены равномерно вокруг круга. Все целые числа, сравнимые по модулю n, занимают одни и те же точки в круге. Положительные и отрицательные целые числа от Z отображаются в круге одним и тем же способом, соблюдая симметрию между ними.
Пример 2.15
Мы пользуемся сравнением по модулю в нашей ежедневной жизни; например, мы применяем часы, чтобы измерить время. Наша система часов использует арифметику по модулю 12. Однако вместо 0 мы берем отсечку 12, так что наша система часов начинается с 0 (или 12 ) и идет до 11. Поскольку наши сутки длятся 24 часа, мы считаем по кругу два раза и обозначаем первое вращение как утро до полудня, а второе — как вечер после полудня.
Три Z, могут также быть определены для набора Zn. Результат, возможно, должен быть отображен в Zn с использованием операции по модулю, как это показано на рис. 2.13.
(рис 2.13) Бинарные операции в Zn Фактически применяются два набора операторов: первый набор — один из a и b ) могут быть членами Z или Zn.
Пример 2.16
Выполните следующие операторы (поступающие от Zn ):
а. Сложение 7 и 14 в Z15
б. Вычитание 11 из 7 в Z13
в. Умножение 11 на 7 в Z20
Решение
Ниже показаны два шага для каждой операции:
(14+7) mod 15 -> (21) mod 15 = 6 (7–11) mod 13 -> (-4) mod 13 = 9 (7x11) mod 20 -> (77) mod 20 = 17
Пример 2.17
Выполните следующие операции (поступающие от Zn ):
a. Сложение 17 и 27 в Z14
b. Вычитание 43 из 12 в Z13
c. Умножение 123 на -10 в Z19
Решение
Ниже показаны два шага для каждой операции:
(17 + 27) mod 14 -> (44) mod 14 = 2 (12 – 43) mod 13 -> (–31) mod 13 = 8 ((123) x (–10)) mod 19 -> (–1230) mod 19 = 5
Мы уже упоминали, что два входа для трех Z или Zn. Следующие свойства позволяют нам сначала отображать два входа к Zn (если они прибывают от Z ) перед выполнением этих трех
(рис 2.14) Свойства оператора mod
Первое свойство: (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 x b) mod n = [(a mod n) x (b mod n)] mod n
Рисунок 2.14 показывает процесс до и после применения указанных выше свойств. Хотя по рисунку видно, что процесс с применением этих свойств более длинен, мы должны помнить, что в криптографии мы имеем дело с очень большими целыми числами. Например, если мы умножаем очень большое целое число на другое очень большое целое число, которое настолько большое, что не может быть записано в компьютере, то применение вышеупомянутых свойств позволяет уменьшить первые два операнда прежде, чем начать умножение. Другими словами, перечисленные свойства позволяют нам работать с меньшими числами. Этот факт станет понятнее при обсуждении экспоненциальных операций в последующих лекциях.
Пример 2.18
Следующие примеры показывают приложение вышеупомянутых свойств.
Пример 2.19
В арифметике мы часто должны находить остаток от степеней числа 10 при делении на целое число. Например, мы должны найти 10 mod 3, 102 mod 3, 103 mod 3, и так далее. Мы также должны найти 10 mod 7, 102 mod 7, 103 mod 7, и так далее. Третье свойство модульных операторов, упомянутое выше, делает жизнь намного проще.
10n mod x = (10 mod x)n Применение третьего свойства n раз.
Мы имеем
10 mod 3 = 1 -> 10n mod 3 = (10 mod 3)n = 1 10 mod 9 = 1 -> 10n mod 9 = (10 mod 9)n = 1 10 mod 7 = 3 -> 10n mod 7 = (10 mod 7)n = 3n mod 7
Пример 2.20
Мы уже говорили, что в арифметике остаток от целого числа, разделенного на 3, такой же, как остаток от деления суммы его десятичных цифр. Другими словами, остаток от деления 6371 равен остатку от деления суммы его цифр (17), на 3. Мы можем доказать, что это утверждение использует свойства модульного оператора. Запишем целое число как сумму его цифр, умноженных на степени 10.
a = an10n +………+ a1101 + a0100 Например: 6371 = 6 x 103 + 3 x 102+ 7 x 101+ 1 x 100
Теперь мы можем применить модульную операцию к двум сторонам равенства и использовать результат предыдущего примера, где остаток 10n mod 3 равен 1.
a mod 3 = (an x 10n +…+ a1 x 101+ a0 x 100) mod 3 = (an x 10n) mod 3 +…+ (a1 x 101) mod 3 + (a0 x 100 mod 3) mod 3 = (an mod 3) x (10n mod 3) +…+ (a1 mod 3) x (101 mod 3) + (a0 mod 3) x (100 mod 3) mod 3 = ((an mod 3) +…+ (a1 mod 3) + (a0 mod 3)) mod 3 = (an +…+ a1 + a0) mod 3
Когда мы работаем в модульной арифметике, нам часто нужно найти операцию, которая позволяет вычислить величину, обратную заданному числу. Мы обычно ищем аддитивную инверсию (оператор, обратный сложению) или мультипликативную инверсию (оператор, обратный умножению).
В Zn два числа a и b аддитивно инверсны друг другу, если b = n – a. Например,
В Zn аддитивная инверсия числу a может быть вычислена как b = n – a. Например, аддитивная инверсия 4 в Z10 равна 10 – 4 = 6.
Обратите внимание, что в модульной арифметике каждое число имеет аддитивную инверсию, и эта инверсия уникальна; каждое число имеет одну и только одну аддитивную инверсию. Однако инверсия числа может быть непосредственно тем же самым числом.
Пример 2.21
Найдите все взаимно обратные пары по сложению в Z10.
Решение
Даны шесть пар аддитивных инверсий — (0, 0), (1, 9), (2, 8), (3, 7), (4, 6) и (5, 5). В этом списке 0 — инверсия самому себе; так же и 5. Обратите внимание: аддитивные инверсии обратны друг другу; если 4 — аддитивная инверсия 6, тогда 6 — также аддитивная инверсия числу 4.
В Zn два числа a и b мультипликативно инверсны друг другу, если
Например, если модуль равен 10, то мультипликативная инверсия 3 есть 7. Другими словами, мы имеем $$(3 \times 7)\bmod 10 \equiv 1$$.
Может быть доказано, что a имеет мультипликативную инверсию в Zn, если только НОД(n, a) = 1. В этом случае говорят, что a и n взаимно простые.
Пример 2.22
Найти мультипликативную инверсию 8 в Z10.
Решение
Мультипликативная инверсия не существует, потому что $$HOD\left( {{\text{1}}0,{\text{8}}} \right) = {\text{2}} \ne {\text{1}}$$. Другими словами, мы не можем найти число между 0 и 9, такое, что при умножении на 8 результат сравним с 1 по mod 10.
Пример 2.23
Найти все мультипликативные инверсии в Z10.
Решение
Есть только три пары, удовлетворяющие условиям существования мультипликативной инверсии: (1, 1), (3, 7) и (9, 9). Числа 0, 2, 4, 5, 6 и 8 не имеют мультипликативной инверсии.
Мы можем проверить, что
(1 x 1) mod 10 = 1 (3 x 7) mod 10 = 1 (9 x 9) mod 10 = 1
Пример 2.24
Найти все мультипликативные обратные пары в Z11.
Решение
Мы имеем следующие пары: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8) и (10, 10). При переходе от Z10 к Z11 число пар увеличивается. При Z11 НОД (11, a) = 1 (взаимно простые) для всех значений a, кроме 0. Это означает, что все целые числа от 1 до 10 имеют мультипликативные инверсии.
a в Zn имеет мультипликативную инверсию тогда и только тогда, если НОД (n, a) = 1(mod n)Расширенный b в Zn, когда даны n и b и инверсия существует. Для этого нам надо заменить первое целое число a на n (модуль). Далее мы можем утверждать, что алгоритм может найти s и t, такие, что $$s \times n + b \times t = HOD\left( {n,b} \right)$$. Однако если мультипликативная инверсия b существует, НОД (n, b) должен быть 1. Так что уравнение будет иметь вид
Теперь мы применяем операции по модулю к обеим сторонам уравнения. Другими словами, мы отображаем каждую сторону к Zn. Тогда мы будем иметь
(s x n + b x t) mod n =1 mod n [(s x n) mod n] + [(b x t) mod n] = 1 mod n 0 + [(b x t) mod n ] = 1 (b x t) mod n =1 -> Это означает, что t – это мультипликативная инверсия b в Zn
Обратите внимание, что $$[(s \times n)\bmod n]$$ на третьей строке — 0, потому что, если мы делим $$(s \times n)n$$, частное — s, а остаток — 0.
b в Zn , когда даны n и b и НОД (n, b) = 1 .
Мультипликативная инверсия .Рисунок 2.15 показывает, как мы находим мультипликативную инверсию числа, используя расширенный
(рис 2.15) Применение расширенного алгоритма Евклида для поиска мультипликативной инверсииПример 2.25
Найти мультипликативную инверсию 11 в Z26.
Решение
Мы используем таблицу, аналогичную одной из тех, которые мы уже применяли прежде при данных r1 = 26 и r2 = 11. Нас интересует только значение t.
| q | r1 | r2 | r | t1 | t2 | t |
|---|---|---|---|---|---|---|
| 2 | 26 | 11 | 4 | 0 | 1 | -2 |
| 2 | 11 | 4 | 3 | 1 | -2 | 5 |
| 1 | 4 | 3 | 1 | -2 | 5 | -7 |
| 3 | 3 | 1 | 0 | 5 | -7 | 26 |
| 1 | 0 | -7 | 26 |
НОД (26, 11) = 1, что означает, что мультипликативная инверсия 11 существует. Расширенный t1 = (–7).
Мультипликативная инверсия равна (–7) mod 26 = 19. Другими словами, 11 и 19 — мультипликативная инверсия в Z26. Мы можем видеть, что $$(11 \times 19)\bmod 26 = 209\bmod 26 = 1$$.
Пример 2.26
Найти мультипликативную инверсию 23 в Z100.
Решение
Мы используем таблицу, подобную той, которую применяли до этого при r1 = 100 и r2 = 23. Нас интересует только значение t.
| q | r1 | r2 | r | t1 | t2 | t |
|---|---|---|---|---|---|---|
| 4 | 100 | 23 | 8 | 0 | 1 | -4 |
| 2 | 23 | 8 | 7 | 1 | -4 | 19 |
| 1 | 8 | 7 | 1 | -4 | 9 | -13 |
| 7 | 7 | 1 | 0 | 9 | -13 | 100 |
| 1 | 0 | -13 | 100 |
НОД (100, 23) = 1, что означает, что инверсия 23 существует. Расширенный Евклидов алгоритм дает t1 =-13. Инверсия — (–13) mod 100 = 87. Другими словами, 13 и 87 — мультипликативные инверсии в Z100. Мы можем видеть, что $$(23 \times 87)\bmod 100 = 2001\bmod 100 = 1$$.
Пример 2.27
Найти мультипликативную инверсию 12 в Z26.
Решение
Мы используем таблицу, подобную той, которую мы применяли раньше при r1 = 26 и r2 = 12.
| q | r1 | r2 | r | t1 | t2 | t |
|---|---|---|---|---|---|---|
| 2 | 26 | 12 | 2 | 0 | 1 | |
| 6 | 12 | 2 | 0 | 1 | -2 | |
| 2 | 0 | -2 | 13 |
$$HOD\left( {{\text{26}},{\text{12}}} \right) = {\text{2}} \ne {\text{1}}$$, что означает отсутвствие для числа 12 мультипликативной инверсии в Z26
Рисунок 2.16 показывает две таблицы для сложения и умножения. При сложении таблиц каждое целое число имеет аддитивную инверсию. Обратные пары могут быть найдены, если результат их сложения — ноль. Мы имеем (0, 0), (1, 9), (2, 8), (3, 7), (4, 6) и (5, 5). При умножении таблиц мы получаем только три мультипликативных пары (1, 1), (3, 7) и (9, 9). Пары могут быть найдены, когда результат умножения равен 1. Обе таблицы симметричны по диагонали, от левой вершины к нижней вершине справа. При этом можно обнаружить свойства коммутативности для сложения и умножения ( a+b = b+a и $$a \times b = b \times a$$ ). Таблица сложения также показывает, что каждый ряд или колонка может поменяться с другим рядом или колонкой. Для таблицы умножения это неверно.
(рис 2.16) Таблицы сложения и умножения для Z10
В криптографии мы часто работаем с инверсиями. Если отправитель посылает целое число (например, ключ для шифрования слова), приемник применяет инверсию этого целого числа (например, ключ декодирования). Если это действие (алгоритм шифрования/декодирования) является сложением, множество Zn может быть использовано как множество возможных ключей, потому что каждое целое число в этом множестве имеет аддитивную инверсию. С другой стороны, если действие (алгоритм шифрования/декодирования) — умножение, Zn не может быть множеством возможных ключей, потому что только некоторые члены этого множества имеют мультипликативную инверсию. Нам нужно другое множество, которое является подмножеством Zn и включает в себя только целые числа, и при этом в Zn они имеют уникальную мультипликативную инверсию. Это множество обозначается Zn*. Рисунок 2.17 показывает некоторые
случаи двух множеств. Обратите внимание, что множество Zn*
может быть получено из таблицы умножения типа показанной на рис. 2.16.
Каждый член Zn имеет аддитивную инверсию, но только некоторые члены имеют мультипликативную инверсию. Каждый член Zn* имеет мультипликативную инверсию, но только некоторые члены множества имеют аддитивную инверсию.
Zn , когда необходимы аддитивные инверсии; мы должны использовать Zn* , когда необходимы мультипликативные инверсии.(рис 2.17) Некоторые множества Zn и Zn*
Криптография часто использует еще два множества: Zp, и Zp*. Модули в этих двух множествах — простые числа. Простые числа будут обсуждаться в следующих лекциях; пока можно сказать, что простое число имеет только два делителя: целое число 1 и само себя.
Множество Zp — то же самое, что и Zn, за исключением того, что n — простое число. Zp содержит все целые числа от 0 до p – 1. Каждый элемент в Zp имеет аддитивную инверсию; каждый элемент кроме 0 имеет мультипликативную инверсию.
Множество Zp* — то же самое, что Zn*, за исключением того, что Zp* содержит все целые числа от 1 до p – 1. Каждый элемент в Zp имеет аддитивную и мультипликативную инверсии. Zp* очень хороший кандидат, когда мы нуждаемся во множестве, которое поддерживает аддитивную и мультипликативную инверсии.
Ниже показаны два множества, когда p = 13.
Z13 = {0,1,2,3,4,5,6,7,8,9,10,11,12},
Z13* = {1,2,3,4,5,6,7,8,9,10,11,12},
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.