Pseudocode of one round of the Miller-Rabin test Represent n-1 as d * 2^s, with d odd (by factoring 2s out) Pick an integer a in the range [2, n-2] miller_rabin(n,a) x = a^d mod n if x == 1 or x == n-1 return 1 (probable prime) for r = 1 .. s-1 x = x^2 mod n if x == 1 return 0 (composite) if x == n-1 return 1 (probable prime) end for return 0 (composite)