restart; mrtest:=proc(n::integer) description "Use the Miller-Rabin test to determine primality of n"; #option trace: local i,m,p,q,a,b,c,test; #Test to bypass program for even n if n mod 2 = 0 then print ("Composite at b_0"); else #First write n-1 as 2^i(m) where m is odd; i:=0; m:=n-1; while irem(m,2,'q')=0 do i:=i+1;m:=q; od; #test b_0 to check primality; test:=rand(2..n-2); a:=test(); b:=a&^m mod n; if b=(1 mod n) or b=(-1 mod n) then p:=Prime; else #loop to test consecutive squares p:=null; for c from 1 to i-1 while p=null do b:=b^2 mod n; if b=1 mod n then p:=Composite; end if; if b=(-1 mod n) then p:=Prime; #p:=1; end if; od; if p=null then print("n failed - composite"); else print(p); end if; end if; end if; end: mrtest(747439858795906654771360002896929079267707323373546785194641045803773607346874936749186616307713020243381794908645198588502728623246331630320599344857318413168189046214545712007555274775357286517811927018722850879174509115563873494516447402088336157351185521620031112618626557163273345997014219403319); SSZQcmltZUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2Ig== Check with Maple isprime(747439858795906654771360002896929079267707323373546785194641045803773607346874936749186616307713020243381794908645198588502728623246331630320599344857318413168189046214545712007555274775357286517811927018722850879174509115563873494516447402088336157351185521620031112618626557163273345997014219403319); SSV0cnVlRyUqcHJvdGVjdGVkRw==