Probabilistic Algorithm

• Problem: Is n prime ?

• No polynomial algorithm.
• Can't prove it doesn't exist !

• Theorem.(Wilsopn) p : prime <=> (p-1)! = -1 (mod p)
• Theorem.(Euler) p: prime => Aexp(p-1) = 1 (mod p) 1<= a<=p-1
  
• Proposition. n: composite => | { A | Aexp(n-1) = 1 (mod n) 1<=a<=n-1} | < (n-1)/2
  
• 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)

• Input n => output: composite ( correct )

  : prime ( correct: Pr>= 1/2 )
  wrong: Pr < 1/2

• Repeat 100 times

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