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

Рисунок 3.2
   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) mod 8 = 24 mod Φ = 16 mod 8 = 0
а для х = 3 :      34   mod 8 = 81 mod Φ = 1.Генерация псевдослучайных
последовательностей (ПСП) чисел и бит