Материал: Лекция 2 Генерирование простых чисел [восстановлен]

Скачать

Заказать новую работу

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

Лекция 2

1.Математический базис КОК

2.Генерирование простых чисел

Малая теорема Ферма

Если p – простое число и p не делит a, то a p−1 =1mod p

Доказательство. Заметим, что 0, a, 2a, … , (p – 1)a различны по

mod p. В противном случае, если предположить, что i a = j a mod p , при i ≠ j, то (i – j)a = 0mod p и поэтому p делит(i - j)a . Но поскольку p не делит a и i, j < p , то сделано неверное предположение, и тогда числа 0, a, 2a, … , (p – 1)a составляют всего лишь перестановку чисел

1, 2, … , p - 1. Следовательно, справедливы следующие равенства: a 2a (p −1)a = a p−1 (p −1)!mod p

1 2 ( p −1) = ( p −1)!mod p

a p−1 (p −1)!mod p =(p −1)!mod p

Отсюда следует, что

Сокращая обе стороны тождества на (p-1)! получаем : ap-1 -1 = 0 mod p .

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

Определение 3. Пусть n – целое натуральное число, тогда

 

 

 

функцией Эйлера

ϕ

(n)

 

 

называется количество целых

 

 

 

неотрицательных чисел, меньших n

и взаимно простых с n,

 

 

 

т. е.: ϕ(n)=#{0 ≤ b < n; gcd(b, n)=1}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

где

#{X}

 

 

 

 

означает количество элементов множества X.

 

 

1.

Свойства:

 

 

 

 

,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ϕ(1) =1

 

 

 

,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.

ϕ(p)= p −1

 

если р –простое число.

n

 

 

1

 

 

 

 

 

 

3.

)

= p

 

− p

 

 

 

 

 

или

 

ϕ(p

n

)= p

 

 

 

 

 

 

 

 

 

ϕ( p

n

n

n−1

 

 

 

 

 

1−

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

p

 

 

 

 

 

 

 

Функция Эйлера мультипликативна

 

 

 

ϕ(m n)=ϕ(m) ϕ(n)

 

 

 

α

α

2

p

α

s )

 

 

α

−1

p

α

2

−1

p

α

s−1

 

( p −1)

( p −1) ( p

 

−1)

ϕ( p

1 p

2

s

 

= p

1

 

2

 

 

s

 

 

s

 

1

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

2

 

Другая запись свойства 4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

α1

−

 

 

 

α2

 

 

 

 

 

 

αr

−

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ϕ(n)= p1

1

 

 

 

p2

 

1 −

 

 

 

 

...pr

1

 

 

 

 

= n∏ 1 −

 

 

 

 

 

 

 

 

 

 

 

p1

 

 

 

 

 

 

 

p2

 

 

 

 

 

pr

 

 

 

p

 

n

 

p

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

n = pα1 pα2

pαs

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

2

 

 

 

 

 

 

 

s

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ТеоремаЭйлера (обобщение теоремы Ферма)

‪ Если gcd(a,m) = 1 , то aϕ(m) =1mod, m

‪ где ϕ(m) – функция Эйлера [1].

‪

‪ Теорема Ферма – это частный случай теоремы Эйлера. Действительно, если m = p – простое число, то по теореме Эйлера ϕ(p)= p −1, что и дает утверждение теоремы Ферма: ap-1 = 1 mod p.

‪

‬ Утверждение 1. (Полезное для ускорения вычисления степени по модулю.)

Если gcd(a, m) = 1, n' = n modϕ(m) , то a n' mod m = a n mod m [3].

‬

‬ Утверждение 2. (Полезное для анализа стойкости криптосистем с открытым

ключом.) Пусть n = p q , где p q – простые числа. p ≠ q

Тогда

числа p и q можно найти, если известно n и ϕ(n)= (p −1) (q −1)

 

‬

 

‬

Доказательство. Будем рассматривать p, q как пару неизвестных целых

 

чисел, для которых задано их произведение p q = n и известна сумма p+q ,

 

поскольку n +1−φ(n)= p q +1−(p −1) (q −1)= p +q = 2b , где b – некоторое целое

 

число.

‬

‬ Два числа, сумма которых равна 2b , а произведение равно n, являются очевидно корнями уравнения x2 −2bx +n = 0 (теорема Виета). Тогда корни квадратного уравнения и есть необходимые числа p и q:

‬ .

 

 

 

‬

p = b +

b2 +n2 ; q = b − b2 +n2

‬

Сложность решения этого уравнения – O(log3 n)
Источник: https://studfile.net/preview/16531039/

Смотрите также:

_РГР № 1 (2)
00338
05 Дифиллобатриоз
ДПП-22-17-1_Лопатина_ПЗ2_ПАСБ
Метод нейтралізації
Обобщающее задание по курсу