|
D.12.2.18 MillerRabin
Procedure from library crypto.lib (see crypto_lib).
- 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
Example:
| LIB "crypto.lib";
bigint x=2;
x=x^787-1;
MillerRabin(x,3);
==> 0
|
|