Pollard-Rho( n )
1. i <-- 1
2. x1 <-- Random( 0, n-1 )
3. y <-- x1
4. k <-- 2
5. while True
6.     do  i <-- i + 1
7.         xi <-- xi-12 - 1 mod n
8.         d <-- GCD( y - xi, n )
9.         if  d != 1 AND  d != n
10.              then  Print d
11.         if   i = k
12.              then  y <-- xi
13.                     k <-- 2k

Fermat's Little Theorem: If p is prime and a is not a multiple of p, then   ap-1 = 1 mod p

A composite number n that satisfies    an-1 = 1 mod n is called a base-a pseudoprime.
For example: 341, 561, 645, 1105

Carmichael numbers are pseudoprime to all bases
For example: 561, 1105, 1729

Miller-Rabin( n, s )
1. for j <-- 1 to s
2.     do  a <-- Random( 1, n-1 )
3.         if Witness( a, n )
4.             then return Composite
5. return Prime

Witness( a, n )
1. factor n - 1 as 2t * u where u is odd (possibly composite)
2. x0 <-- au  mod n
3. for i <-- 1 to t
4.     do  xi <-- xi-12 mod n
5.         if   xi = 1 AND xi-1 != 1 AND xi-1 != n-1
6.              then return True
7. if  xt != 1
8.     then return True
9. return False

### References:

Applied Cryptography,
by Bruce Schneier,
Wiley, 1996

Introduction to Algorithms, second edition
by Cormen, Leiserson, Rivest, and Stein
MIT Press/McGraw-Hill, 2001