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

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

A composite number n that satisfies    a^n-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 2^t * u where u is odd (possibly composite)
2. x₀ <-- a^u  mod n
3. for i <-- 1 to t
4.     do  x_i <-- x_i-1² mod n
5.         if   x_i = 1 AND x_i-1 != 1 AND x_i-1 != n-1
6.              then return True
7. if  x_t != 1
8.     then return True
9. return False

References:

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