5.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 делит (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 бит и более).

{ Пример. Нужно вычислить а ⁸ mod n.

Не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:

(а • а • а • а • а • а • а • а) mod n.

Вместо этого выполняют три малых умножения и три малых приведения по модулю:

((а ² mod n.)² mod n.)² mod n.

Тем же способом вычисляют

а ¹⁶ mod n. = (((а ² mod n.)² mod n.)² mod n.)² mod n. }

Вычисление

а ^х mod n,

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

х = 12 ₍₁₀₎ = 11001 ₍₂₎.

Поэтому 25 = 2 ⁴ + 2 ³ + 2 ⁰.

Тогда

а ²⁵ mod n. = (а • а ²⁴) mod n. = (а • а ⁸ • а ¹⁶) mod n =

= (а • ((а ²) ²) ² • (((а ²) ²) ² ) ²) mod n = ((((а ² • а) ²) ² ) ² • а) mod n.

При накоплении промежуточных результатов потребуется только шесть умножений:

(((((((а ² mod n) • а) mod n)² mod n)² mod n)² mod n) • а) mod n.

Этот метод уменьшает трудоемкость вычислений до 1,5хk операций в стреднем, где k – длина числа в битах.

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