Help:=proc(): print(`ModPol(p,x,h), ord1(a,r)`): 
print(`Check31(M), AKS(n)`):
end:


#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(FAIL):
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:

AKS:=proc(n) local r:

if not type(n,integer) or n<=1 then
 ERROR(`bad input`):
fi:

for r from 2 to trunc(evalf(log(n)/log(2))) do
 if type(n^(1/r), integer) then 
RETURN(false)
   
 fi:
od:

#To be continued

end: