#Dennis Hou's version, try DennisAKS(n) # Our old AKS, including improvements from Josh #ModPol(p,x,h): inputs a polynomial p in the variable #x and another polynomial h, in x, finds #p mod h ModPol:=proc(p,x,h) rem(p,h,x): end: with(numtheory): #ord1(a,r): the smallest pos. integer k such that #a^k mod r =1 (gcd(a,r)=1) ord1:=proc(a,r) local S,i: if gcd(a,r)<>1 then RETURN(1): fi: S:=sort(divisors(phi(r))): for i from 1 to nops(S) do if a^S[i] mod r =1 then RETURN(S[i]): fi: od: ERROR(`Nothing found`): end: #Check31(M) checks Lemma 3.1. in the AKS paper #for m between 7 and M Check31:=proc(M) local m: evalb({seq(evalb(lcm(seq(i,i=1..m))>=2^m),m=7..M)}={true}): end: #AKS(n): the Agrawal-Kayal-Saxena famous #primaity-testing algoritm: #Dramatically improved by Josh Loftus (the one who (so far) #didn't murder anyone) DennisAKS:=proc(n) local r,a,asya,X, J,Asya: if not type(n,integer) or n<=1 then ERROR(`bad input`): fi: #step 1 for r from 2 to trunc(evalf(log(n)/log(2))) do if type(root(n,r), integer) then RETURN(false) fi: od: #step 2 for r from trunc(evalf(4*log[2](n)^2)) while ord1(n,r) <= trunc(evalf(4*log[2](n)^2)) do od: #step 3 for a from 2 to r do if 10 then RETURN(false): fi: od: true: end: #AKS(n): the Agrawal-Kayal-Saxena famous #primaity-testing algoritm: #Dramatically improved by Josh Loftus (the one who (so far) #didn't murder anyone) AKS:=proc(n) local r,a,asya,X, J,Asya: if not type(n,integer) or n<=1 then ERROR(`bad input`): fi: #step 1 for r from 2 to trunc(evalf(log(n)/log(2))) do if type(root(n,r), integer) then RETURN(false) fi: od: #step 2 for r from trunc(evalf(4*log[2](n)^2)) while ord1(n,r) <= trunc(evalf(4*log[2](n)^2)) do od: #step 3 for a from 2 to r do if 10 then RETURN(false): fi: od: true: end: fastexpand:=proc(n) local i, j, p: j:=1: p:=0: for i from 1 to n/2-(n+1 mod 2) do j:=(n-i+1)/i*j mod n: p:=p + j*X^(n-i)*J^i + j*X^i*J^(n-i) mod n: od: end: ------=_20100311114100_31746--