Модульная математика

Уравнение деления ( ), рассмотренное в предшествующей секции, имеет два входа ( a и n ) и два выхода ( q и r ). В модульной математике мы интересуемся лишь одним из выходов — остатком r . Мы не заботимся о личном q . Иными словами, когда мы делим a на n , мы интересуемся лишь тем, что значение остатка равно r . Это предполагает, что мы можем представить изображение вышеупомянутого уравнения как бинарный оператор с 2-мя входами a и n и одним выходом r .

Операции по модулю

Вышеупомянутый бинарный оператор назван оператором по модулю и обозначается как mod . 2-ой вход ( n ) назван модулем. Вывод r назван вычетом. Набросок 2.9 указывает отношение деления по сопоставлению с оператором по модулю.

Как показано на рис. 2.9, оператор по модулю ( mod ) выбирает целое число ( a ) из огромного количества Z и положительный модуль ( n ). Оператор описывает неотрицательный остаток ( r ).

Мы можем сказать, что

Отыскать итог последующих операций:

Мы отыскиваем вычет 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 .

Система вычетов: Zn

Итог операции по модулю n — постоянно целое число меж 0 и n — 1 . Иными словами, итог a mod n — постоянно неотрицательное целое число, наименьшее, чем n . Мы можем сказать, что операция по модулю делает набор, который в модульной математике можно осознавать как систему меньших вычетов по модулю n, либо Z_n . Но мы должны держать в голове, что хотя существует лишь одно огромное количество целых чисел ( Z ), мы имеем нескончаемое число множеств вычетов ( Z_n ), но только одно для всякого значения n . Набросок 2.10 указывает огромное количество Z_n и три огромного количества Z₂ , Z₆ и Z₁₁ .

Сопоставления

В криптографии мы нередко используем понятие сопоставления заместо равенства. Отображение Z в Z_n не показываются «один в один». Нескончаемые элементы огромного количества Z могут быть отображены одним элементом Z_n . К примеру, итог 2 mod 10 = 2 , 12 mod 10 = 2 , 22 mod 10 = 2 , и так дальше. В модульной математике целые числа, подобные 2 , 12 , и 22 , именуются сопоставимыми по модулю 10 (mod 10) . Для того чтоб указать, что два целых числа сравнимы, мы используем оператор сопоставления ( ). Мы добавляем mod n к правой стороне сопоставления, чтоб найти значение модуля и создать равенство правильным. К примеру, мы пишем:

Набросок 2.11 указывает принцип сопоставления. Мы должны разъяснить несколько положений.

a. Оператор сопоставления припоминает оператор равенства, но меж ними есть различия. 1-ое: оператор равенства показывает элемент Z самого на себя; оператор сопоставления показывает элемент Z на элемент Z_n . 2-ое: оператор равенства указывает, что наборы слева и справа соответствуют друг дружке «один в один», оператор сопоставления — «почти все — одному».

б. Обозначение ( mod n ), которое мы вставляем с правой стороны оператора сопоставления, обозначает признак огромного количества ( Z_n ). Мы должны добавить это обозначение, чтоб показать, какой модуль употребляется в отображении. Знак, применяемый тут, не имеет такого же самого значения, как бинарный оператор в уравнении деления. Иными словами, знак mod в выражении 12 mod 10 — оператор; а сочетание ( mod 10 ) в сопоставлении значит, что набор — Z₁₀ .

Система вычетов

Система вычетов [a] , либо [a]_n , — огромное количество целых чисел, сравнимых по модулю n . Иными словами, это набор всех целых чисел, таковых, что x = a (mod n) . К примеру, если n = 5 , мы имеем огромное количество из 5 частей [0] , [1] , [2] , [3] и [4] , таковых как это показано ниже:

Целые числа в наборе [0] все дают остаток 0 при делении на 5 (сравнимы по модулю 5 ). Целые числа в наборе [1] все дают остаток 1 при делении на 5 (сравнимы по модулю 5 ), и так дальше. В любом наборе есть один элемент, именуемый минимальным (неотрицательным) вычетом. В наборе [0] это элемент 0 ; в наборе [1] — 1 , и так дальше. Набор, который указывает все меньшие вычеты: Z₅ = <0, 1, 2, 3, 4>. Иными словами, набор Z_n — набор всех меньших вычетов по модулю n.

Радиальная система обозначений

Понятие «сопоставление» быть может лучше раскрыто при использовании круга в качестве модели. Так же, как мы применяем линию, чтоб показать распределение целых чисел в Z , мы можем применять круг, чтоб показать распределение целых чисел в Z_n .

Набросок 2.12 дозволяет сопоставить два этих подхода. Целые числа от 0 до n–1 размещены умеренно вокруг круга. Все целые числа, сравнимые по модулю n , занимают одни и те же точки в круге. Положительные и отрицательные целые числа от Z показываются в круге одним и этим же методом, соблюдая симметрию меж ними.

Мы пользуемся сопоставлением по модулю в нашей каждодневной жизни; к примеру, мы применяем часы, чтоб измерить время. Наша система часов употребляет математику по модулю 12 . Но заместо 0 мы берем отсечку 12 , так что наша система часов начинается с 0 (либо 12 ) и идет до 11 . Так как наши день продолжаются 24 часа, мы считаем по кругу дважды и обозначаем 1-ое вращение как утро до пополудни, а 2-ое — как вечер опосля пополудни.

Операции в Zn

Три бинарных операции ( сложение, вычитание и умножение ), которые мы обсуждали для Z , могут также быть определены для набора Z_n . Итог, может быть, должен быть отображен в Z_n с внедрением операции по модулю, как это показано на рис. 2.13.

Практически используются два набора операторов: 1-ый набор — один из бинарных операторов ; 2-ой — операторы по модулю. Мы должны применять круглые скобки, чтоб выделить порядок работ. Как показано на рис. 2.13, входы ( a и b ) могут быть членами Z либо Z_n .

Сделайте последующие операторы (поступающие от Z_n ):

а. Сложение 7 и 14 в Z₁₅

б. Вычитание 11 из 7 в Z₁₃

в. Умножение 11 на 7 в Z₂₀

Ниже показаны два шага для каждой операции:

Сделайте последующие операции (поступающие от Z_n ):

a. Сложение 17 и 27 в Z₁₄

b. Вычитание 43 из 12 в Z₁₃

c. Умножение 123 на -10 в Z₁₉

Ниже показаны два шага для каждой операции:

Характеристики

Мы уже упоминали, что два входа для 3-х бинарных операторов в сопоставлении по модулю могут применять данные из Z либо Z_n . Последующие характеристики разрешают нам поначалу показывать два входа к Z_n (если они прибывают от Z ) перед выполнением этих 3-х бинарных операторов . Заинтригованные читатели могут отыскать подтверждения для этих параметров в приложении Q.

1-ое свойство: (a + b) mod n = [(a mod n) + (b mod n)] mod n

2-ое свойство: (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 указывает процесс до и опосля внедрения обозначенных выше параметров. Хотя по рисунку видно, что процесс с применением этих параметров наиболее длинен, мы должны держать в голове, что в криптографии мы имеем дело с весьма большенными целыми числами. К примеру, если мы умножаем весьма огромное целое число на другое весьма огромное целое число, которое так огромное, что не быть может записано в компе, то применение вышеупомянутых параметров дозволяет уменьшить 1-ые два операнда до этого, чем начать умножение. Иными словами, перечисленные характеристики разрешают нам работать с наименьшими числами. Данный факт станет понятнее при обсуждении экспоненциальных операций в следующих лекциях.

Последующие примеры демонстрируют приложение вышеупомянутых параметров.