#Code by Gloria Liu
#6. [Optional challenge, 5 dolalrs for the best implementation] Implement (in Maple) the Rabin-Miller (pseudo-) primality test
#MillerRabin(p,k): Miller Rabin primality test
#p is an odd number we are checking for primality
#It will print the witness if there is one
#k is the number of t imes we want to check for a non primality witness for p
#Returns false for composite and true for (probably) prime
MillerRabin:=proc(p,k) local s,d,i,b,f,a,j,b1:
for i from 1 to k do
 a:=rand(2..p-1)():
 if MRHelper(p,a)=false then
    RETURN(false):
 fi:
od:
true:
end:

MRHelper:=proc(p,a) local s,d,i,b,f,j,b1:
d:=p-1:
s:=0:
while d mod 2=0 do
 d:=d/2:
 s:=s+1:
od:
 b:=a&^d mod p:
 if b = 1 or b = p-1 then RETURN(true): fi:
 for j from 1 to s do
  b1:=b&^2 mod p:
  if b1 = -1 mod p then
   #Not all of result is -1 so a is not a witness
   RETURN(true):
   f:=false:
   break:
  fi:
  b:=b1:
 od:
false:
end: