Computer Security and Cryptography

13.8 TESTING IF AN INTEGER IS A PRIME

RSA encipherment requires prime numbers for its implementation. Fermat's Little Theorem is the basis for testing if n is a prime; if it is, then aⁿ⁻¹ = 1 (modulo N) for every a for which 1 = gcd{a, n}.

• If n is an odd composite number and 1 ≤ a < n such that aⁿ⁻¹ ≠ 1 (modulo N), then a is a Fermat witness to the compositeness of n.
• If n is an odd composite number and 1 ≤ a < n such that aⁿ⁻¹ = 1 (modulo N), then n is a pseudoprime to base a and a is a Fermat liar to the primality of n.

13.8.1 Fermat's Primality Test

n is an odd integer and t ≥ 1.For i = 1 to t do

(a) Choose a random integer a with 2 ≤ a ≤ n − 2

(b) Compute r = aⁿ⁻¹ (modulo n)

(c) If r ≠ 1, Return (“Composite”).

Return(“Prime”)Fermat's Primality Test may falsely conclude n is a prime. A composite integer n is a Carmichael number (discovered by R. D. Carmichael in 1910) if a^n−l = 1 (modulo N) for every a for which 1 ≤ a ≤ n−1.

Proposition 13.8:

13.8a	n is a Carmichael number if and only if n is square-free an p − 1 divides n − 1 for every prime divisor of n;
13.8b	Each Carmichael number has at least three distinct prime factors;
13.8c	There are an infinite number of Carmichael numbers;
13.8d	The smallest Carmichael number is n = 561 = 3 × 11 × 17 and · · · for Triple Jeopardy; there are only 105,212 Carmichael numbers ≤1015.

Suppose n is composite; a primality test that computes the value aⁿ⁻¹ (modulo N) until an a is found yielding a residue ≠ 1 may fail for ...