Miller's Theorem

Thm [ERH]: for any integer n if

 

pseudo(1,n)=pseudo(2,n)=...=pseudo(c log n, n) = T

 

then n is prime.

Rabin's Theorem

Thm : for any composite n

 

#{ a | 1<a<n and pseudo(a,n)= T } < n/4