D.12.3.16 MillerRabin

Usage:

MillerRabin(n,k);

Return:

1 if n is prime, 0 else

Note:

probabilistic test of Miller-Rabin with k loops to test if n is prime. Using the theorem: If n is prime, n-1=2^s*r, r odd, then powerN(a,r,n)=1 or powerN(a,r*2^i,n)=-1 for some i

LIB "crypto.lib";
bigint x=2;
x=x^787-1;
MillerRabin(x,3);
==> 0