Правила арифметики вычетов

 

Правила арифметики вычетов похожи на обычную арифметику:

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,

3. (a * b) mod n = ((a mod n) * (b mod n)) mod n,

4. (a (b+c)) mod n = (((a*b) mod n) + ((a*c) mod n)) mod n.

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

Один из таких приемов называется цепочкой сложения, либо методом дво­ичных квадратов и умножения.

Рассмотрим примеры.

Пример 1. Пример преобразования выражения :

a² mod n = (a*a) mod n = ((a mod n) * (a mod n)) mod n = (a mod n)² mod n.

Рассмотрим достоинство такого преобразования на числовом примере. Пусть а =50, n=2. Тогда

a² mod n =50² mod 2 = 2500 mod 2 = 0,

т.е. промежуточный результат вычисления (возведение в степень) давало число 2500.

То же самое путем преобразования:

a² mod n =((a mod n)² mod n = ((0)² mod 2 = 0,

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

Пример 2. Некоторые цепочки сложения:

a⁴ mod n = (a²*a²) mod n = ((a² mod n)*(a² mod n)) mod n = ((a² mod n)² mod n.

a⁸ mod n = (a⁴*a⁴) mod n = ((a⁴ mod n)*(a⁴ mod n)) mod n =

((((a² mod n)² mod n)* (((a² mod n)² mod n)) mod n = ((a² mod n)² mod n)² mod n.

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