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

Модулярная арифметика часто изучается в школе как "арифметика часов". Если отсчитать 14 часов от 3 часов после полудня, то получится 5 часов утра следующего дня

3 + 14=5(mod12) или

(3+14) mod 12 = 5

Это арифметика по модулю 12

Обычная запись в модулярной арифметике

а º b(mod n)

читается так " а сравнимо с b по модулю n " Это соотношение справедливо для целых значении a b и n и n¹0, если и только если

а = b + k´n

для некоторого целого k

Отсюда, в частности, следует

n|(a-b)

Это читается как n делит (a-b)

Если а º b(mod n)

то b называют вычетом числа а по модулю n.

Операцию нахождения вычета числа а по модулю n

a(mod n)

называют приведением числа а по модулю n или приведением по модулю.

В нашем примере (3+14) mod 12 = 17 mod 12 =5 или 17º5(mod l2),

число 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},

но иногда полезны вычеты в диапазоне целых

Заметим что

-12(mod 7) º-5(mod 7) º 2(mod 7) º 9(mod 7) и т.д.

Модулярная арифметика аналогична во многом обычной арифметике, она коммутативна, ассоциативна и дистрибутивна. Точнее говоря, целые числа по модулю n с использованием операции сложения и умножения, образуют коммутативное кольцо при соблюдении законов ассоциативности, коммутативности и дистрибутивности.

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

(а + b) mod n = [a(mod n) + D(mod n)] mod n

(a - b) mod n = [a(mod n) - D(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 бит и более).

Например, если нужно вычислить

a⁸ mod п,

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

(а´а´а´а´а´а´а´а) mod п

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

((a² mod п)² mod п)² mod n

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

a¹⁶ mod n= (((a² mod n)² mod n² mod n)² mod n

Вычисление

а^x mod n,

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

х = 25 ₍₁₀₎®1 1 0 0 1₍₂₎, поэтому 25 = 2⁴ + 2³ + 2⁰

Тогда

a²⁵ mod n = (а´a²⁴) mod п=(а´а⁸´а¹⁶) mod п =

= а´((а²)²)² ´(((a²)²}²)² mod n - ((((а² * а)²)²)²´a) mod n.

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

(((((((a² mod n)´a) mod n)² mod n)² mod n)² mod п)´a) mod п.

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

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