Home Online Manual
Top
Back: rho
Forward: SolowayStrassen
FastBack: atkins_lib
FastForward: hyperel_lib
Up: crypto_lib
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

D.12.3.16 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