Open in CoCalc
%html <h1><center>Алгоритм Агравала—Каяла—Саксены (AKS) %html <h3> Test AKS %html Если существует $r\in\mathbb{Z}$ такое, что $o_r(n)>\log^2 n$ и для любого $a$ от 1 до $\left\lfloor\sqrt{\varphi(r)}\log_2(n)\right\rfloor$ выполняется %html $$ (x+a)^n\equiv(x^n+a)\pmod{x^r-1,\;n}, $$ %html то $n$ — либо простое число, либо степень простого числа. %html $o_r(n)$ — показатель числа $n$ по модулю $r$ - такое $k$, что $n^k \equiv 1 \pmod n$ %html $\log_2$ — двоичный логарифм 1111 %html $\varphi(\cdot)$ — функция Эйлера %html Сравнение по двум модулям вида $a(x)\equiv b(x)\pmod{h(x),\;n}$ для многочленов $a(x),\;b(x)\in\mathbb{Z}[x]$ означает, что существует $g(x)\in\mathbb{Z}[x]$ такой, что все коэффициенты многочлена $a(x)-b(x)-g(x)h(x)$ кратны $n$, где $\mathbb{Z}[x]$ — кольцо многочленов от $x$ над целыми числами. %html Данное утверждение похоже на малую теорему Ферма, однако малую теорему Ферма можно проверить за $O(n)$, в то время как AKS можно проверить быстрее, выбрав правильное $r$.

Алгоритм Агравала—Каяла—Саксены (AKS)

Test AKS

Если существует rZr\in\mathbb{Z} такое, что or(n)>log2no_r(n)>\log^2 n и для любого aa от 1 до φ(r)log2(n)\left\lfloor\sqrt{\varphi(r)}\log_2(n)\right\rfloor выполняется(x+a)n(xn+a)(modxr1,  n), (x+a)^n\equiv(x^n+a)\pmod{x^r-1,\;n}, то nn — либо простое число, либо степень простого числа.or(n)o_r(n) — показатель числа nn по модулю rr - такое kk, что nk1(modn)n^k \equiv 1 \pmod nlog2\log_2 — двоичный логарифм 1111φ()\varphi(\cdot) — функция ЭйлераСравнение по двум модулям вида a(x)b(x)(modh(x),  n)a(x)\equiv b(x)\pmod{h(x),\;n} для многочленов a(x),  b(x)Z[x]a(x),\;b(x)\in\mathbb{Z}[x] означает, что существует g(x)Z[x]g(x)\in\mathbb{Z}[x] такой, что все коэффициенты многочлена a(x)b(x)g(x)h(x)a(x)-b(x)-g(x)h(x) кратны nn, где Z[x]\mathbb{Z}[x] — кольцо многочленов от xx над целыми числами.Данное утверждение похоже на малую теорему Ферма, однако малую теорему Ферма можно проверить за O(n)O(n), в то время как AKS можно проверить быстрее, выбрав правильное rr.
import time # Kostul, I hate this thing -- tell me how normal human beings should do it def make_global(func): globals()[func.__name__] = func make_global(make_global) __global_time__ = 0 akslog_show = 0 def akslog_reset_time(): global __global_time__ __global_time__ = time.time() make_global(akslog_reset_time) def akslog(formatstr, *args): if 'akslog_show' not in globals() or akslog_show == 0: return global __global_time__ print "%.2f" % (time.time() - __global_time__), formatstr.format(*args) make_global(akslog) akslog_reset_time()
%html Некоторые дополнительные функции для работы алгоритма. %html Проверка того, что предоставленное число - полная степень числа def check_comp_perfect_power(n): for b in range(2, log(n, 2) + 1): a = n ^ (1 / b) print a if a.is_integer(): return True return False make_global(check_comp_perfect_power) print "31 полная степень числа -", check_comp_perfect_power(31) print "25 полная степень числа -", check_comp_perfect_power(25)
Некоторые дополнительные функции для работы алгоритма.Проверка того, что предоставленное число - полная степень числа
31 полная степень числа - sqrt(31) 31^(1/3) 31^(1/4) False 25 полная степень числа - 5 True
%html Поиск $r$, такого что $o_r(n)>\log^2 n$ по определению %html $o_r(n)$ — показатель числа $n$ по модулю $r$ - такое $k$, что $n^k \equiv 1 \pmod n$ %html При оценке сложности используется, что $r \leqslant max(3,\lceil\log^5 n\rceil)$, что может быть улучшено при помощи алгоритма Ленстры-Померанса до $\log^2 n$ def find_ord(n): r = 2 log2n = int(log(n, 2) ^ 2) # ord is such k that foreach n^k = 1 mod r # we need k > log2(n) while (True): r += 1 A = Integers(r) nr = A(n) is_ord = True for k in range(1, log2n + 1): # 1 means ord is done, 0 is not coprime if nr ** k == 1 or nr ** k == 0: is_ord = False break if is_ord: break return r make_global(find_ord) print find_ord(3571) print "Подходящее r для числа 31 -", find_ord(1111111111111111111) print "Подходящее r для числа 3571 -", find_ord(3571) print "Подходящее r для числа 3469 -", find_ord(3469) print "Подходящее r для числа 2 -", find_ord(2) print "Подходящее r для числа -1 -", find_ord(-1)
Поиск rr, такого что or(n)>log2no_r(n)>\log^2 n по определениюor(n)o_r(n) — показатель числа nn по модулю rr - такое kk, что nk1(modn)n^k \equiv 1 \pmod nПри оценке сложности используется, что rmax(3,log5n)r \leqslant max(3,\lceil\log^5 n\rceil), что может быть улучшено при помощи алгоритма Ленстры-Померанса до log2n\log^2 n
163 Подходящее r для числа 31 - 3659 Подходящее r для числа 3571 - 163 Подходящее r для числа 3469 - 157 Подходящее r для числа 2 - 3 Подходящее r для числа -1 - 3
%html Проверка наличия делителей у числа до заданного def check_comp_gcd_foreach(n, r): for a in range(3, min(r, n-1) + 1, 2): if gcd(a, n) != 1: return True return False make_global(check_comp_gcd_foreach) print "Делители 31 до 29 -", check_comp_gcd_foreach(31, 29) print "Делители 15 до 4 -", check_comp_gcd_foreach(15, 4) print "Делители 15 до 2 -", check_comp_gcd_foreach(15, 2)
Проверка наличия делителей у числа до заданного
Делители 31 до 29 - False Делители 15 до 4 - True Делители 15 до 2 - False
%html Проверка самого AKS теста до заданного значения %html Расчет осуществляется при помощи SageMath кольца полиномов над $\mathbb{Z}_n$ с делителем $x^r-1$ def get_aks_poly(n, r, a): # Setup polynomial ring in Integers(n) R = PolynomialRing(Integers(n), 'x') x, = R.gens() divisor = x^r - 1 # Define function that will calc remainder def rem(val): print(val) print(divisor) _, rem = val.quo_rem(divisor) print(rem, "\n") return rem # Optimal power using method of divide and conquer - важно понять почему стандартное тормозит. def optpow(val, power): if power <= 8: return rem(val ^ power) else: if power % 2 == 0: powval = optpow(val, power/2) return rem(powval * powval) else: power -= 1 powval = optpow(val, power/2) return rem(powval * powval * val) # Do it lhs = optpow(x + a, n) rhs = rem(x ^ n + a) return lhs - rhs def check_comp_aks_test(n, r, maxval): for a in range(1, maxval + 1): poly = get_aks_poly(n, r, a) if poly: return True return False make_global(check_comp_aks_test) print "Проверка числа 31, r=29 до a=26, число составное -", check_comp_aks_test(31, 29, 26)
Проверка самого AKS теста до заданного значенияРасчет осуществляется при помощи SageMath кольца полиномов над Zn\mathbb{Z}_n с делителем xr1x^r-1
Проверка числа 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
%html <h3>Алгоритм AKS</h3> %html Ввод: целое число $n>1$. %html Если $n=a^b$ для целых чисел $a>0$ и $b>1$, вернуть "составное". %html Найдем наименьшее $r$, такое что $o_r(n)>(\log_2(n))^2$. %html Если $1< gcd(a,n) < n $ для некоторого $a\leqslant r$, вернуть "составное". %html Если $n\leqslant r$, вернуть "простое". %html Если для всех $a$ от 1 до $\left\lfloor\sqrt{\varphi(r)}\log(n)\right\rfloor$ верно, что $(x+a)^n\equiv x^n+a\pmod{x^r-1,\;n}$, вернуть "простое". %html Иначе вернуть "составное". %html Сложность $\widetilde{O}(\log n^{10.5})$, Ленстра-Померанс $\widetilde{O}(\log n^6)$ def check_prime_aks(n): reset_time() if check_comp_perfect_power(n): akslog("AKS: Is Perfect Power") return False r = find_ord(n) akslog("AKS: Using r {0}", r) if check_comp_gcd_foreach(n, r): akslog("AKS: Divisor detected smaller than r {0}", r) return False if n <= r: akslog("AKS: {0} <= {1}", n, r) return True maxval = int(sqrt(euler_phi(r)) * log(n, 2)) akslog("AKS: Maxval {0}", maxval) if check_comp_aks_test(n, r, maxval): akslog("AKS: AKS Test Failed") return False akslog("AKS: Prime") return True make_global(check_prime_aks) print "Число 11939 простое -", check_prime_aks(11939)

Алгоритм AKS

Ввод: целое число n>1n>1.Если n=abn=a^b для целых чисел a>0a>0 и b>1b>1, вернуть "составное".Найдем наименьшее rr, такое что or(n)>(log2(n))2o_r(n)>(\log_2(n))^2.Если 1<gcd(a,n)<n1< gcd(a,n) < n для некоторого ara\leqslant r, вернуть "составное".Если nrn\leqslant r, вернуть "простое".Если для всех aa от 1 до φ(r)log(n)\left\lfloor\sqrt{\varphi(r)}\log(n)\right\rfloor верно, что (x+a)nxn+a(modxr1,  n)(x+a)^n\equiv x^n+a\pmod{x^r-1,\;n}, вернуть "простое".Иначе вернуть "составное".Сложность O~(logn10.5)\widetilde{O}(\log n^{10.5}), Ленстра-Померанс O~(logn6)\widetilde{O}(\log n^6)
Число 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
%html Тестирование для алгоритма AKS для первых 1000 чисел и сравнение с эталоном count = 100 is_failed = False for n in range(3, count, 2): answer = is_prime(n) aksAnswer = check_prime_aks(n) if answer != aksAnswer: is_failed = True print "Wrong answer for ", n if is_failed: %html AKS выдал неверные ответы else: %html Ошибок не найдет
Тестирование для алгоритма 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
data = [] P = Primes() n = P.unrank(2000) def nextprime(n, P): for i in range(20): n = P.next(n + 1) return n for i in range(100): n = nextprime(n, P) timestart = time.time() result = check_prime_aks(n) timeend = time.time() t = timeend - timestart x = float(log(n)) y = float(log(t)) print result, x, y data.append((x, y)) # Fit data to linear model _ = var('k, b, x') model(x) = k * x + b sol = find_fit(data, model) f(x) = model(b=sol[0].rhs(), k=sol[1].rhs()) a = plot([]) a += plot(f(x), x, data[0][0], data[-1][0]) a += points(data, color='darkgreen', pointsize=50, aspect_ratio=1) show(a)
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