Арифметика остатков

Определение 1.  a сравнимо с b по модулю n
,                                                                                                       (1)  
если R(a) = R(b).
Отношение (1) есть отношение эквивалентности. Это отношение разбивает  на непересекающиеся классы вычетов. Класс вычетов будем обозначать [a], .
  -коммутативное кольцо:        
1. [a] + [b] = [a + b]   корректно определенная коммутативная, ассоциативная операция.
2. [a]  [b] = [a  b]   корректно определенная коммутативная, ассоциативная операция.
3. ([a] + [b])  [c] = [a  c] + [b  c].
Докажем, что результат операции сложения не зависит от выбора представителей (корректность). 
a + b = nq +r  +nq + r, r + r = n + r,
 +  = nq +r +nq + r, r+ r = n + r.
Для операции умножения корректность доказывается аналогично.
Лемма 1.
. 
Доказательство непосредственно следует из (1).
Лемма 2.  В любом классе вычетов существует единственное  наименьшее неотрицательное число.
Д о к а з а т е л ь с т в о.
a  N,   a [a]   r <  n   r  [a].
Если  a > n: a = qn + r, r < n, то a – r = qn  и по лемме 1 r  [a]. 
Докажем единственность от противного. Предположим, что   r  r, r < n, r  [a]. Пусть r < r, тогда  r - r = qn > 0   q  1, но так как r < n, r < n, то r - r < n – противоречие. Следовательно,  не существует  такого r. Лемма доказана.
С другой стороны,  
Следующие свойства остатков важны для дальнейшего.
1.	(c  d)(modb) = (c(modb)  d(modb))(modb),
где    {+, -,  }.
2. (a(c+d))(modb) = ( (ac)(modb) + (ad)(modb))(modb).
Использование вычетов в криптографии основано на существовании алгоритма быстрого возведения в степень.
Пусть 

где (mod n) – остаток от деления  на n, следовательно, его проще возводить в квадрат, чем число . Таким образом, любая степень числа два позволяет быстрее возводить в степень, если последовательно приводить промежуточные результаты по модулю n.

Если х – произвольное число, то существует представление

и тогда возведение в степень опирается на быстрый алгоритм возведения в степень числа 2:

Пример 1.

Можно доказать, что возведение в степень k требует в среднем 1,5k операций.