CoCalc -- Collaborative Calculation in the Cloud
SharedAKS.sagewsOpen 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