%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 с делителем xr−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