Probabilistic Algorithm

@

TestPrime(n)
choose a = { 1,2,3,.....,n-1} randomly
if (a,n)=1 then return (composite)
if Aexp(n-1) != 1 (mod n) then return(composite) else return (prime)

Pr(wrong) < 1 / 2exp100 !!!