Алгоритм Агравала—Каяла—Саксены (AKS)
Test AKS
Если существует такое, что и для любого от 1 до выполняется
то — либо простое число, либо степень простого числа.
— показатель числа по модулю - такое , что
— двоичный логарифм 1111
— функция Эйлера
Сравнение по двум модулям вида для многочленов означает, что существует такой, что все коэффициенты многочлена кратны , где — кольцо многочленов от над целыми числами.
Данное утверждение похоже на малую теорему Ферма, однако малую теорему Ферма можно проверить за , в то время как AKS можно проверить быстрее, выбрав правильное .
Некоторые дополнительные функции для работы алгоритма.
Проверка того, что предоставленное число - полная степень числа
31 полная степень числа - sqrt(31)
31^(1/3)
31^(1/4)
False
25 полная степень числа - 5
True
Поиск , такого что по определению
— показатель числа по модулю - такое , что
При оценке сложности используется, что , что может быть улучшено при помощи алгоритма Ленстры-Померанса до
163
Подходящее r для числа 31 - 3659
Подходящее r для числа 3571 - 163
Подходящее r для числа 3469 - 157
Подходящее r для числа 2 - 3
Подходящее r для числа -1 - 3
Проверка наличия делителей у числа до заданного
Делители 31 до 29 - False
Делители 15 до 4 - True
Делители 15 до 2 - False
Проверка самого AKS теста до заданного значения
Расчет осуществляется при помощи SageMath кольца полиномов над с делителем
Проверка числа 31, r=29 до a=26, число составное - x^7 + 7*x^6 + 21*x^5 + 4*x^4 + 4*x^3 + 21*x^2 + 7*x + 1
x^15 + 15*x^14 + 12*x^13 + 21*x^12 + x^11 + 27*x^10 + 14*x^9 + 18*x^8 + 18*x^7 + 14*x^6 + 27*x^5 + x^4 + 21*x^3 + 12*x^2 + 15*x + 1
x^2 + 1
x^2 + 1
x^7 + 14*x^6 + 22*x^5 + x^4 + 2*x^3 + 21*x^2 + 14*x + 4
x^15 + 30*x^14 + 17*x^13 + 13*x^12 + 16*x^11 + 27*x^10 + 28*x^9 + 10*x^8 + 20*x^7 + 7*x^6 + 27*x^5 + 2*x^4 + 22*x^3 + 3*x^2 + 23*x + 1
x^2 + 2
x^2 + 2
x^7 + 21*x^6 + 3*x^5 + 15*x^4 + 14*x^3 + 19*x^2 + 19*x + 17
x^15 + 14*x^14 + 15*x^13 + 9*x^12 + 19*x^11 + 20*x^10 + 7*x^9 + 27*x^8 + 19*x^7 + 3*x^6 + 24*x^5 + 13*x^4 + 13*x^3 + 9*x^2 + 26*x + 30
x^2 + 3
x^2 + 3
x^7 + 28*x^6 + 26*x^5 + 8*x^4 + x^3 + 21*x^2 + 28*x + 16
x^15 + 29*x^14 + 6*x^13 + 11*x^12 + 8*x^11 + 27*x^10 + 25*x^9 + 9*x^8 + 5*x^7 + 19*x^6 + 27*x^5 + 4*x^4 + 26*x^3 + 24*x^2 + 27*x + 1
x^2 + 4
x^2 + 4
x^7 + 4*x^6 + 29*x^5 + 4*x^4 + 20*x^3 + 29*x^2 + 7*x + 5
x^15 + 13*x^14 + 21*x^13 + 21*x^12 + 5*x^11 + 24*x^10 + 14*x^9 + 28*x^8 + 16*x^7 + 14*x^6 + 11*x^5 + 25*x^4 + 21*x^3 + 29*x^2 + 3*x + 1
x^2 + 5
x^2 + 5
x^7 + 11*x^6 + 12*x^5 + 27*x^4 + 7*x^3 + 19*x^2 + 7*x + 6
x^15 + 28*x^14 + 29*x^13 + 10*x^12 + 25*x^11 + 20*x^10 + 14*x^9 + 15*x^8 + 28*x^7 + 17*x^6 + 24*x^5 + 26*x^4 + 21*x^3 + 10*x^2 + 13*x + 30
x^2 + 6
x^2 + 6
x^7 + 18*x^6 + 6*x^5 + 8*x^4 + 25*x^3 + 12*x^2 + 28*x + 28
x^15 + 12*x^14 + 30*x^13 + 11*x^12 + 14*x^11 + 11*x^10 + 25*x^9 + 8*x^8 + 25*x^7 + 19*x^6 + 24*x^5 + 20*x^4 + 26*x^3 + 11*x^2 + 11*x + 1
x^2 + 7
x^2 + 7
x^7 + 25*x^6 + 11*x^5 + 2*x^4 + 16*x^3 + 21*x^2 + 25*x + 2
x^15 + 27*x^14 + 24*x^13 + 26*x^12 + 4*x^11 + 27*x^10 + 19*x^9 + 5*x^8 + 9*x^7 + 25*x^6 + 27*x^5 + 8*x^4 + 11*x^3 + 6*x^2 + 29*x + 1
x^2 + 8
x^2 + 8
x^7 + x^6 + 27*x^5 + 2*x^4 + 18*x^3 + 29*x^2 + 25*x + 10
x^15 + 11*x^14 + 11*x^13 + 26*x^12 + 20*x^11 + 24*x^10 + 19*x^9 + 25*x^8 + 8*x^7 + 25*x^6 + 11*x^5 + 14*x^4 + 11*x^3 + 30*x^2 + 12*x + 1
x^2 + 9
x^2 + 9
x^7 + 8*x^6 + 23*x^5 + x^4 + 10*x^3 + 29*x^2 + 14*x + 20
x^15 + 26*x^14 + 22*x^13 + 13*x^12 + 18*x^11 + 24*x^10 + 28*x^9 + 19*x^8 + 4*x^7 + 7*x^6 + 11*x^5 + 19*x^4 + 22*x^3 + 15*x^2 + 17*x + 1
x^2 + 10
x^2 + 10
x^7 + 15*x^6 + 30*x^5 + 23*x^4 + 5*x^3 + 2*x^2 + 28*x + 13
x^15 + 10*x^14 + 26*x^13 + 20*x^12 + 9*x^11 + 7*x^10 + 25*x^9 + 17*x^8 + x^7 + 12*x^6 + 11*x^5 + 24*x^4 + 26*x^3 + 4*x^2 + 24*x + 30
x^2 + 11
x^2 + 11
x^7 + 22*x^6 + 17*x^5 + 30*x^4 + 19*x^3 + 19*x^2 + 14*x + 24
x^15 + 25*x^14 + 23*x^13 + 18*x^12 + 28*x^11 + 20*x^10 + 28*x^9 + 29*x^8 + 7*x^7 + 24*x^6 + 24*x^5 + 21*x^4 + 22*x^3 + 18*x^2 + 22*x + 30
x^2 + 12
x^2 + 12
x^7 + 29*x^6 + 15*x^5 + 15*x^4 + 9*x^3 + 2*x^2 + 19*x + 22
x^15 + 9*x^14 + 13*x^13 + 9*x^12 + 10*x^11 + 7*x^10 + 7*x^9 + 24*x^8 + 2*x^7 + 3*x^6 + 11*x^5 + 3*x^4 + 13*x^3 + 8*x^2 + 6*x + 30
x^2 + 13
x^2 + 13
x^7 + 5*x^6 + 24*x^5 + 2*x^4 + 28*x^3 + 12*x^2 + 25*x + 19
x^15 + 24*x^14 + 27*x^13 + 26*x^12 + 7*x^11 + 11*x^10 + 19*x^9 + x^8 + 14*x^7 + 25*x^6 + 24*x^5 + 9*x^4 + 11*x^3 + 26*x^2 + 21*x + 1
x^2 + 14
x^2 + 14
x^7 + 12*x^6 + 13*x^5 + 15*x^4 + 8*x^3 + 10*x^2 + 19*x + 23
x^15 + 8*x^14 + 3*x^13 + 9*x^12 + 2*x^11 + 4*x^10 + 7*x^9 + 11*x^8 + 10*x^7 + 3*x^6 + 27*x^5 + 15*x^4 + 13*x^3 + 14*x^2 + 30*x + 30
x^2 + 15
x^2 + 15
x^7 + 19*x^6 + 13*x^5 + 16*x^4 + 8*x^3 + 21*x^2 + 19*x + 8
x^15 + 23*x^14 + 3*x^13 + 22*x^12 + 2*x^11 + 27*x^10 + 7*x^9 + 20*x^8 + 10*x^7 + 28*x^6 + 27*x^5 + 16*x^4 + 13*x^3 + 17*x^2 + 30*x + 1
x^2 + 16
x^2 + 16
x^7 + 26*x^6 + 24*x^5 + 29*x^4 + 28*x^3 + 19*x^2 + 25*x + 12
x^15 + 7*x^14 + 27*x^13 + 5*x^12 + 7*x^11 + 20*x^10 + 19*x^9 + 30*x^8 + 14*x^7 + 6*x^6 + 24*x^5 + 22*x^4 + 11*x^3 + 5*x^2 + 21*x + 30
x^2 + 17
x^2 + 17
x^7 + 2*x^6 + 15*x^5 + 16*x^4 + 9*x^3 + 29*x^2 + 19*x + 9
x^15 + 22*x^14 + 13*x^13 + 22*x^12 + 10*x^11 + 24*x^10 + 7*x^9 + 7*x^8 + 2*x^7 + 28*x^6 + 11*x^5 + 28*x^4 + 13*x^3 + 23*x^2 + 6*x + 1
x^2 + 18
x^2 + 18
x^7 + 9*x^6 + 17*x^5 + x^4 + 19*x^3 + 12*x^2 + 14*x + 7
x^15 + 6*x^14 + 23*x^13 + 13*x^12 + 28*x^11 + 11*x^10 + 28*x^9 + 2*x^8 + 7*x^7 + 7*x^6 + 24*x^5 + 10*x^4 + 22*x^3 + 13*x^2 + 22*x + 1
x^2 + 19
x^2 + 19
x^7 + 16*x^6 + 30*x^5 + 8*x^4 + 5*x^3 + 29*x^2 + 28*x + 18
x^15 + 21*x^14 + 26*x^13 + 11*x^12 + 9*x^11 + 24*x^10 + 25*x^9 + 14*x^8 + x^7 + 19*x^6 + 11*x^5 + 7*x^4 + 26*x^3 + 27*x^2 + 24*x + 1
x^2 + 20
x^2 + 20
x^7 + 23*x^6 + 23*x^5 + 30*x^4 + 10*x^3 + 2*x^2 + 14*x + 11
x^15 + 5*x^14 + 22*x^13 + 18*x^12 + 18*x^11 + 7*x^10 + 28*x^9 + 12*x^8 + 4*x^7 + 24*x^6 + 11*x^5 + 12*x^4 + 22*x^3 + 16*x^2 + 17*x + 30
x^2 + 21
x^2 + 21
x^7 + 30*x^6 + 27*x^5 + 29*x^4 + 18*x^3 + 2*x^2 + 25*x + 21
x^15 + 20*x^14 + 11*x^13 + 5*x^12 + 20*x^11 + 7*x^10 + 19*x^9 + 6*x^8 + 8*x^7 + 6*x^6 + 11*x^5 + 17*x^4 + 11*x^3 + x^2 + 12*x + 30
x^2 + 22
x^2 + 22
x^7 + 6*x^6 + 11*x^5 + 29*x^4 + 16*x^3 + 10*x^2 + 25*x + 29
x^15 + 4*x^14 + 24*x^13 + 5*x^12 + 4*x^11 + 4*x^10 + 19*x^9 + 26*x^8 + 9*x^7 + 6*x^6 + 27*x^5 + 23*x^4 + 11*x^3 + 25*x^2 + 29*x + 30
x^2 + 23
x^2 + 23
x^7 + 13*x^6 + 6*x^5 + 23*x^4 + 25*x^3 + 19*x^2 + 28*x + 3
x^15 + 19*x^14 + 30*x^13 + 20*x^12 + 14*x^11 + 20*x^10 + 25*x^9 + 23*x^8 + 25*x^7 + 12*x^6 + 24*x^5 + 11*x^4 + 26*x^3 + 20*x^2 + 11*x + 30
x^2 + 24
x^2 + 24
x^7 + 20*x^6 + 12*x^5 + 4*x^4 + 7*x^3 + 12*x^2 + 7*x + 25
x^15 + 3*x^14 + 29*x^13 + 21*x^12 + 25*x^11 + 11*x^10 + 14*x^9 + 16*x^8 + 28*x^7 + 14*x^6 + 24*x^5 + 5*x^4 + 21*x^3 + 21*x^2 + 13*x + 1
x^2 + 25
x^2 + 25
x^7 + 27*x^6 + 29*x^5 + 27*x^4 + 20*x^3 + 2*x^2 + 7*x + 26
x^15 + 18*x^14 + 21*x^13 + 10*x^12 + 5*x^11 + 7*x^10 + 14*x^9 + 3*x^8 + 16*x^7 + 17*x^6 + 11*x^5 + 6*x^4 + 21*x^3 + 2*x^2 + 3*x + 30
x^2 + 26
x^2 + 26
False
Алгоритм AKS
Ввод: целое число .
Если для целых чисел и , вернуть "составное".
Найдем наименьшее , такое что .
Если $1< gcd(a,n) [removed]
Если , вернуть "простое".
Если для всех от 1 до верно, что , вернуть "простое".
Иначе вернуть "составное".
Сложность , Ленстра-Померанс
Число 11939 простое -
*** WARNING: Code contains non-ascii characters ***
Error in lines 31-31
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 1, in <module>
File "", line 2, in check_prime_aks
NameError: global name 'reset_time' is not defined
Тестирование для алгоритма AKS для первых 1000 чисел и сравнение с эталоном
*** WARNING: Code contains non-ascii characters ***
Error in lines 4-9
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 3, in <module>
File "", line 2, in check_prime_aks
NameError: global name 'reset_time' is not defined
sqrt(17579)
17579^(1/3)
17579^(1/4)
17579^(1/5)
17579^(1/6)
17579^(1/7)
17579^(1/8)
17579^(1/9)
17579^(1/10)
17579^(1/11)
17579^(1/12)
17579^(1/13)
17579^(1/14)
True 9.7744602868 -0.46220369887
sqrt(17789)
17789^(1/3)
17789^(1/4)
17789^(1/5)
17789^(1/6)
17789^(1/7)
17789^(1/8)
17789^(1/9)
17789^(1/10)
17789^(1/11)
17789^(1/12)
17789^(1/13)
17789^(1/14)
True 9.78633556773 -0.225245690501
sqrt(17977)
17977^(1/3)
17977^(1/4)
17977^(1/5)
17977^(1/6)
17977^(1/7)
17977^(1/8)
17977^(1/9)
17977^(1/10)
17977^(1/11)
17977^(1/12)
17977^(1/13)
17977^(1/14)
True 9.79684844205 -0.418010983057
sqrt(18149)
18149^(1/3)
18149^(1/4)
18149^(1/5)
18149^(1/6)
18149^(1/7)
18149^(1/8)
18149^(1/9)
18149^(1/10)
18149^(1/11)
18149^(1/12)
18149^(1/13)
18149^(1/14)
Error in lines 8-17
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 4, in <module>
File "", line 16, in check_prime_aks
File "", line 3, in check_comp_aks_test
File "", line 20, in get_aks_poly
File "sage/rings/polynomial/polynomial_template.pxi", line 630, in sage.rings.polynomial.polynomial_zmod_flint.Polynomial_template.__pow__ (build/cythonized/sage/rings/polynomial/polynomial_zmod_flint.cpp:12216)
celement_pow(&r.x, &(<Polynomial_template>self).x, e, NULL, (<Polynomial_template>self)._cparent)
File "./sage/libs/flint/nmod_poly_linkage.pxi", line 529, in sage.rings.polynomial.polynomial_zmod_flint.celement_pow (build/cythonized/sage/rings/polynomial/polynomial_zmod_flint.cpp:5665)
sig_on()
File "src/cysignals/signals.pyx", line 98, in cysignals.signals.sig_raise_exception
KeyboardInterrupt