Материал: Лекция 2 Генерирование простых чисел [восстановлен]
Полиномиальный тест AKS
• Предложенв 2002г.индийскимиматематиками
Agrawal M., Kayal N., Saxena N.
• Центральная идея опирается на следующийфакт.
Натуральное n при условии НОД(a,n)=1, является |
||||||||||||
( |
() −∑ n |
=( () |
|
− |
|
( |
|
|
) |
|
||
|
n |
n |
) |
k n−k |
|
)modn |
n |
|
(1) |
|||
|
|
k |
|
|
|
n |
|
|
||||
простым в том случае, когда |
|
|
|
|||||||||
|
x −a = |
C x |
−a |
mod n = |
|
x −a |
|
|
modn |
|||
i=0
=(xn −a an−1) mod n = (xn −a 1) mod n
•Для уменьшения трудоемкости−1 вычисленийвыражение
(1)делят(на−многочлен= ( − и находят остатки−1)). (2)
) )modn, mod( . ) ,
Теорема 2. Пусть натуральное n и простое r |
||
Ii) n не делится на |
больше( ) |
2, |
таковы, что |
|
|
i) порядок n в группе |
|
|
a 1, √ 2 ,
простые числа меньшиеr,
Iii) тождество (2) выполняетсядля всех
Тогда n – степеньпростого числа.
Алгоритм AKS
1. Делимость5 n на числа от 2 до проверяется≤ 5 в лоб;
2. Ищется r , для которого выполняется(i)в теореме 2;
3. Проверяется (iii);
4. Проверяется не извлекается ли из n целый корень.
Доказано~, что сложность7,5 алгоритма довольно высока поэтому практической ценности алгоритм пока не имеет.