Информационная безопасность и защита информации: Конспект лекций. Будко В.Н. - 28 стр.

Выражение (5) равносильно утверждению, что остатки от делений ‘a‘ и ‘b’ на N равны
17 ≡5 (mod 12)
означает, что
17 mod 12 = 5
5 mod 12 = 5
Для N = 12 полный набор вычетов есть {0, 1, 2, … 11}
Выражение a ≡ 1 (mod N) определяет все целые положительные ‘a’, остатки от деления
которых на N равны 1.

3.2. Основные свойства
     18. a mod a = 0                                                              (6)
     19. (a + b) mod N = (a mod N + b mod N) mod N                                (7)
     20. (a – b) mod N = (a mod N – b mod N) mod N                                (8)
     21. (a * b) mod N = (a mod N) * (b mod N) mod N                              (9)
Доказательство — прямая подстановка. Например:
a = 60, b = 63, N = 32
(60 * 63) mod 32 =3780 mod 32 =3780 – 32 * 118 = 4
L mod N = L – N * INT(L/N)
60 mod 32 = 28, 63 mod 32 = 31
(28 * 31) mod 32 = 868 mod 32 = 4
Следствие:
Если m = a + b + c, то:
     22. xm mod N = xa+b+c mod N = (xaxbxc) mod N =
= [(xa mod N)*(xb mod N)*(xc mod N)] mod N                                 (10)
     23. (a*(b+c)) mod N = ((a*b) mod N + (a*c) mod N) mod N               (11)
         a⋅i             a       i
     24. x mod N = (x mod N) mod N)                                               (12)
                               2⋅3            6
Действительно, например 5            mod 11 = 5 mod 11 = 5
 2
5 mod 11 = 3
(52 mod 11)3 mod 11 = 33 mod 11 = 27 mod 11 = 5
Формулы (9), (10), (12) удобно использовать для расчета по mod N больших чисел
превосходящих разрядность ЭВМ.
Например: x53 mod N
Разложим 53 на двоичные сомножители 1, 2, 4, 8, 32, 64, ….
x53 = x(32+16+4+1)
Надо сачала найти x2, x4 = (x2)2, x8 = (x4)2, x16 = (x8)2, x32 = (x16)2.
Это 5 операций умножения.
Теперь надо последовательно умножить x 32 ⋅ x 16 ⋅ x 4 ⋅ x еще три операции умножения. Все
операции надо делать по модулю N. Получим результат за 8 операций