testing pseudo-primality

pseudo(a,n: integer):boolean

 

IF gcd(a,n)>1 THEN RETURN F

compute s,t such that n-1 = t2s (t odd)

x := at mod n; {expo(a,t,n)}

compute x, x2 mod n, x4 mod n,..., x2s mod n

 

• according to Fermat the last should be "1"

• check that the first time "1" appears in

the sequence it results from squaring "n-1".