Лекции по криптологии / Y06_M01_L04

Лекция 4. Модульная арифметика.

4.1. Вычеты по модулю m. Отношение сравнения. Расширенный алгоритм Эвклида.

Каждое целое число можно разделить с остатком на натуральное число : , <.

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

Определение. Два целых числа и сравнимы по модулю , если их разность делится на . Аналогия – тело, движущееся по окружности, периодически попадает в одну и ту же точку окружности, хотя проходит разный путь. Длины путей «сравнимы по модулю длины окружности».

Отношение сравнимости записывается в виде: , , . Вместо знака сравнения часто используется знак равенства. Кроме того, если это не вызывает недоразумений, указание модуля может отсутствовать.

В соответствии с данным определением, числа, имеющие одинаковые остатки от деления на , сравнимы по модулю .

Если не оговорено противное, то стандартные значения вычетов по модулю , принадлежат множеству (т.н. система наименьших неотрицательных вычетов).

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

Отношение сравнимости позволяет разбить все множество целых чисел на классы. Элементы одного и того же класса имеют одинаковые вычеты по модулю . Очевидно, классы не пересекаются. Поэтому каждому классу соответствует один наименьший неотрицательный вычет и наоборот. Если мы выделим некоторые два класса: и , то вычет суммы или произведения модулю элементов и не зависит от выбора этих элементов, а зависит лишь от выбора классов. Поэтому мы можем построить кольцо, элементами которого являются классы, а операции выполняются через действия над наименьшими неотрицательными вычетами, которые принадлежат соответствующим классам.

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

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

Этот алгоритм предназначен для поиска целочисленного решения ,, уравнения , >, , где и также целые. Очевидно, общий случай сводится к решению подобных уравнений при положительных и .

Рассмотрим схему расширенного алгоритма Эвклида на примере чисел 15 и 25. Мы будем находить остатки и (неполные) частные от деления двух чисел, т.е. пользоваться равенствами вида , где все числа целые и <.

Поскольку должно выполняться неравенство >, то изменим обозначения: , .

Выпишем последовательность строк:

(,).

Пояснение. Делим на с остатком. Получаем: т.е. , откуда , . Проверяем: ? Нет – работаем дальше. Вычисляем : . Формируем очередную строку: .

Исходными данными для шага 2 будут строки (из предыдущего шага) и . С этими строками действуем аналогично.

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

(,)

(,).

При формировании очередной строки, остаток , выписываем решение из данных предыдущего шага:

НОД, , НОД.

4.2. Существование обратного элемента в кольце вычетов.

Алгоритм Эвклида показывает, что для взаимно простых чисел и всегда существует число такое, что .

Такое число называется обратным к по модулю и обозначается .

Действительно, если , то относительно и разрешимо уравнение . Приводя по модулю обе части указанного равенства, получим сравнение , т.е. .

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

Заметим, что если модуль является простым числом , все ненулевые вычеты по модулю взаимно просты с модулем. Поэтому они все обратимы мо умножению в кольце . Следовательно, это кольцо является полем, причем состоящим из элементов. Таким образом, .

По аналогии с кольцом вычетов по модулю , можно построить кольцо вычетов полиномов по модулю нормированного неприводимого полинома над полем .

Для этого достаточно рассмотреть множество остатков от деления всех полиномов с коэффициентами из и заметить, что расширенный алгоритм Эвклида может быть переформулирован для решения уравнения аналогичного , а именно: .

Если положить , то, при , и соотношение , приведенное по модулю дает . Поэтому все ненулевые элементы нашего кольца обратимы, т.е. оно является полем.

Поскольку коэффициенты полиномов вычисляются по правилам арифметики , то число является характеристикой нашего поля . Очевидно, что количество элементов поля равно количеству полиномов, степени меньшей , т.е. конечно. Это значит, что .

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

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

В итоге, мы заключаем, что элементы поля можно рассматривать как - мерные векторы с координатами из подполя .

Число называется степенью расширения .

Элемент поля представляется в поле - мерным вектором (расширенным числом) вида .