Лекция 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) |
1.2. Китайская теорема об остатках
Пусть m1, m2 , , mr числа такие что
Тогда система уравнений
i ≠ j для gcd(m.i , m j )=1
|
x = a |
|
mod m ; |
||
|
|
1 |
1 |
|
|
|
x = a2 |
mod m2 |
; |
||
|
|
|
|
|
|
|
|
|
|
||
x = ar |
mod mr |
|
|||
|
|||||
|
|
имеет решение, и при этом если два числа x' системы, то они удовлетворяют уравнению
|
x' = x'' mod М |
|
|
где M = m1 m2 mr |
|
|
|
(2.6)
и x" решения данной
(2.7)
Доказательство. Докажем однозначность решения по |
mod M = m1 m2 mr |
|||
Предположим, что есть два решения системы (2.6) |
x' и |
x" . Обозначим |
||
y = x' − x" , тогдаy удовлетворяет системе |
|
|
||
y = O mod m ; |
|
|
|
|
1 |
|
|
|
|
y = O mod m2 |
; |
y = O mod M |
|
|
|
|
|
|
|
|
|
|
|
|
y = O mod mr |
|
|
|
|
|
|
|
|
так как m1 , m2 , ..., mr – взаимно простые. Отсюда и следует, что
|
|
|
x' = x'' mod M |
|
|
|
Покажем теперь, как сконструировать хотя бы одно решение x. |
||||||
Обозначим |
M i = |
M |
. Очевидно, что |
gcd(mi , M i )=1 |
, поэтому существует |
|
|
m |
|
|
|||
обратный элементi Ni к Mi по mod mi, т. е. Mi-1 |
= Ni- , M i Ni =1mod mi , |
который может быть найден по алгоритму Евклида для нахождения обратных элементов.
.
Обозначим |
M |
i |
= |
M |
|
|
|
i |
i |
|
|
, поэтому существует обратный |
||
|
|
mi . Очевидно, что |
|
|
|
|||||||||
|
|
|
|
|
|
|
gcd(m |
, M |
)=1 |
|
|
|||
элемент N |
к M |
по mod m , т.е. M |
-1 |
= N |
- |
, M |
i |
N |
i |
=1mod m, который может |
||||
i |
|
|
i |
i |
i |
|
i |
|
|
|
|
i |
||
быть найден по алгоритму Евклида для нахождения обратных элементов. |
||||||||||||||
Положим теперь |
|
|
|
|
|
|
|
|
|
|
||||
r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x = ∑ai Mi N i |
mod M =( a1M1N1 +a2 M2 N2 + +ar Mr Nr )mod M |
i=1
Данное решение будет решением системы (2.6). Действительно, так
как mi делит Mj ,i ≠ j , видно, что все слагаемые будут равны нулю по mod mi, за исключением i-го слагаемого.
Тогда получаем |
x = ai M i Ni |
mod mi |
|
, и поэтому x = aimod mi, при i = 1, |
2, … , r , т.е. x – решение1 системы (2.6).
Пример решения системы уравнений
x = 2 mod 3
x = 3mod 5x = 2 mod 7
1. M = 3 5 7 =105
2. M1 =105 / 3 = 35, M2 =105 / 5 = 21, M3 =105 / 7 =15
3. N1 = 2, N2 =1, N3 =1,
4. x =( 2 35 2 +3 21 1+2 15 1) = 23mod 105
1.3.Цепные дроби
• |
Цепная дробь [a0 |
, a01, , an ] определяется как |
||||||||||
|
формальная сумма |
|
1 |
|
|
|
|
|
|
|
||
|
|
a0 |
= |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
1 |
|
|
|
|
|
|
||||
|
|
|
|
a1 + |
|
|
|
|
|
|
|
|
|
|
|
|
a + |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
2 |
a |
+ |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
a |
||||||||
|
|
|
|
|
|
n−1 |
|
|||||
|
|
|
|
|
|
|
|
n |
||||
• |
Числа a0 , a1, , ak |
k=0,1,…..,n называются неполными |
||||||||||
|
частными цепной дроби, а величины αk =[ak , ak +1, , an ] |
k=0,1,…..,n называются полным частными цепной дроби.
• Числа δk =[a0 , a1, , ak ] называютсяподходящими дробями к цепной дроби
Пример цепной дроби
[−3, 2,1, 4] = −3 + |
|
1 |
|
|
= − |
47 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
13 |
|
|
|
|
|
|
|
|
|
|
|||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
1+ |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Неполные частные имеют вид |
|
|
a 0 = −3 a 1= 2 a 2 =1 |
|
a 3 = 4 |
||||||||||||
полные частные имеют вид |
|
|
|
α0 =[−3, 2,1, 4] = −3 + |
|
1 |
|
|
= − |
47 |
|||||||
|
|
|
|
|
1 |
|
|
13 |
|||||||||
|
|
|
|
|
|
|
|
|
|
2 + |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
1+ |
1 |
|
|
|
|||
|
|
α =[2,1, 4] == 2 + |
|
1 |
= 14 |
|
|
|
4 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
1 |
|
|
|
1 |
1 |
5 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
+ 4 |
|
|
|
|
|
|
|
|
α2 =[1, 4] =1+ 14 = 54
α3 =[4] = 4
Пример цепной дроби
(продолжение)
•Цепная дробь, образованная отбрасыванием всех элементов после некоторого номера k, называется k-ой подходящей дробью
δ0 =[−3] = −3
δ1 =[−3, 2] = −3 + |
1 |
|
= − |
5 |
|
|
||||||
|
|
2 |
|
|
|
|
2 |
|
|
|||
δ2 =[−3, 2,1] = −3 + |
|
|
|
1 |
|
|
= − |
8 |
|
|||
2 |
+ |
1 |
|
3 |
|
|||||||
|
|
|
|
|
|
|
||||||
|
|
1 |
|
|
|
|
|
|
||||
δ3 =[−3, 2,1, 4] = −3 + |
|
|
|
|
1 |
|
|
|
|
= − |
47 |
|
|
|
|
|
|
1 |
|
|
|
13 |
|||
2 |
+ |
|
|
|
|
|
|
|
||||
|
1+ 1 |
|
|
|
|
|||||||
|
|
|
|
|
|
4 |
|
|
|
|
• Подходящие дроби можно представить рациональными |
|||||||||||
числами |
Pk |
k=0,1,…..,n . |
|
|
|
|
|
||||
|
P0 |
= a0 |
Qk |
|
P1 |
= a0a1 +1 |
|
Pk |
|
ak Pk −1 + Pk −2 |
|
δ0 = |
|
δ1 = |
δk = |
= |
для k ≥ 2 |
||||||
Q0 |
|
||||||||||
|
Q1 |
Qk |
|
||||||||
|
1 |
|
|
a1 |
|
|
ak Qk −1 +Qk −2 |
Свойства:
1. P Q |
− P Q |
= (−1)n−1 |
7. Если a =[a0 , a1, , a , ], то |
n n−1 |
n−1 n |
|
δ0 <δ2 < <δ2k < ≤ a ≤ δ2k +1 < <δ3 <δ1 |
2. PnQn−2 − Pn−2Qn = (−1)n−1 an |
3. (PnQn ) =1 |
|
|
|
|
8. |
Если a =[a ,a , ,a , ], то |
|
a−δ |
n |
|
≤ |
1 |
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|||||
4. 1 = Q ≤ Q |
< Q |
< |
|
|
0 1 |
|
|
|
|
QnQn−1 |
1 |
|||
|
|
|
|
|
||||||||||
0 |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
||
5. Если P0 |
>1, то P1 > P2 |
> |
|
|
|
|
|
|
|
|
6. δn −δn−1 = (−1)n−1
QnQn−1