Основные свойства

18. amoda= 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. x^m mod N = x^a+b+c mod N = (x^ax^bx^c) mod N =

= [(x^a mod N)*(x^b mod N)*(x^c mod N)] mod N (10)

23. (a*(b+c)) mod N = ((a*b) mod N + (a*c) mod N) mod N (11)

24. x^ai mod N = (x^a mod N)ⁱ mod N) (12)

Действительно, например 5^23 mod11 = 5⁶mod11 = 5

5²mod11 = 3

(5²mod11)³mod11 = 3³mod11 = 27mod11 = 5

Формулы (9), (10), (12) удобно использовать для расчета по modNбольших чисел превосходящих разрядность ЭВМ.

Например: x⁵³modN

Разложим 53 на двоичные сомножители 1, 2, 4, 8, 32, 64, ….

x⁵³=x^(32+16+4+1)

Надо сачала найти x²,x⁴ = (x²)²,x⁸ = (x⁴)²,x¹⁶ = (x⁸)²,x³² = (x¹⁶)².

Это 5 операций умножения.

Теперь надо последовательно умножить еще три операции умножения. Все операции надо делать по модулюN. Получим результат за 8 операций

Пример 1:

3¹⁹ mod 15 = 3¹⁹ — 15Int(3¹⁹/15) = 1162261467 – 1577484097= 12

19 = 16 + 2 + 1

39 = 27mod15 = 12

126 = 72mod15 = 12

Следствие: если x^a modN= 1, то иx^aimodN= 1

Пример 2:

Общие формулы вычисления больших степеней.

a^bmodN= (aaа…a(bраз)modN) затем применяем формулу (9)

25. F(φ(x)) mod N = F(φ(x) mod N) mod N (13)

Проверка: N = 11,x = 5

26. Свойство коммутативности.

Обозначим x^amodN=F_a(x),x^bmodN=F_b(x)

Будет верно тождество

F_a(F_b(x))modN=F_b(F_a(x))modNдля всехx. (14)

Действительно:

F_a(F_b(x)) = (F_b(x))^amodN= (x^bmodN)^amodN= (см. формулу 13) = (x^b)^amodN=x^bamodN

F_b(F_a(x)) = (F_a(x))^bmodN= (x^amodN)^bmodN= (см. формулу 13) = (x^a)^bmodN=x^abmodN

но x^ba=x^abследовательно иF_a(F_b(x)) =F_b(F_a(x))

27. Теорема Эвклида (300 г. до н.э.)

Если Е и М удовлетворяют условию 0 < EMи НОД(М,Е) = 1, то существует единственное числоD, такое что 0 <D<Mи

E*D  1 (mod M) ((E*D) mod M = 1) (15)

и кроме того Dможет быть вычислено с помощью расширения алгоритма Евклида при нахожденииHOD(M, Е). (Сравни Кнут Д. ”Искусство программирования, ” т. 1 стр. 26, 1976г.

Алгоритм Евклида при нахождении HOD(M,Е).

Рисунок 3.9

28. Функция Эйлера

Φ(N) — функция Эйлера определяет для каждого положительного целого числаNколичество положительных целых чиселiне превышающихNи таких, чтоHOD(i,N) = 1, ПриN= 1 по определению Φ (1) = 1

1 i<N

Найдем, например, Φ(8). Вычислим НОД (i, 8), 1i< 8, (i= 1, 2, …7)

i	1	2	3	4	5	6	7
НОД (i,8)	1	2	1	4	1	2	1

Имеем до 4-х i= 1, 3, 5, 7 НОД (i,8) = 1 следовательно Φ(8) = 4.

Очевидно, что для простого числа Р имеем Φ(Р) = Р – 1, так как простое число не делится нацело на меньшее число. Например, Φ(7) = 7 – 1 = 6, ибо для всех i=1,2,3,4,5,6 НОД(i,7) = 1.

Нетрудно видеть, что для двух неравных простых чисел PиQ

Φ(P*Q) = (P- 1)*(Q– 1) (16)

Например, Φ(6) = Φ(2*3) = 1*2 = 2.

29. Теорема Эйлера

Для любых целых чисел xиN(x<N)

x^Φ(N)  1 (mod N), x^Φ(N) mod N = 1 (17)

при условии, что НОД (x,N) = 1.

Например, для Φ(8) = 4 сравнение (17), будет выполнено только для x= 1,3,5,7 для которых НОД (х,N) = 1.

Действительно, например :

для х = 2 : 2^Φ(8) mod8 = 2⁴modΦ = 16mod8 = 0

а для х = 3 : 3⁴ mod8 = 81modΦ = 1.Генерация псевдослучайных последовательностей (ПСП) чисел и бит