Нахождение обратных чисел в модульной арифметике (по сложению и умножению)

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

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

3 + 14 = 5 (mod12)

или

(3+14) mod 12 = 5

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

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

a º b(mod n)

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

a = b + k * n

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

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

n |(a – b)

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

a º b(mod n)

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

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

a(mod n)

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

В нашем примере

(3+ 14) mod 12 = 17 mod 12 = 5

или

17 º 5 (mod 12),

число 5 является вычетом числа 17 по модулю 12.

Набор целых чисел от 0 до (n-1) называют полным набором вычетов по модулю п. Это означает, что для любого целого а(а>0) его вычет г по модулю 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:

(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

a^x mod n

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

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

a⁸ mod n,

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

(a * a * a * a * a * a * a * a) mod n

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

((a² mod n)² mod n)² mod n.

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

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

 

Вычисление

a^x mod n.

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

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

Тогда

a²⁵ mod n = (a * a²⁴) mod n = (a * a⁸ * a¹⁶) mod n = a * ((a²)²)² * (((a²)²)²)² mod n = ((((a² * a)²)²)² * a) mod n.

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

(((((((a² mod n) * a) mod n)² mod n)² mod n)² mod n) * a) mod n

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

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