Algorithmic Number Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 179

Input : an integer n
Output : a list of p ri me numbers whose product is n
Complexity :

( √ n ) arithmetic operations O

← √ n 1: b , x ← n , i ← 2

2: while x > 1 and i ≤ b do

while i divides x do

3:

print i

4:

x ← x / i

5:

← √ x b

6:

end while 7:

i ← i + 1

8:

9: end while
10: if x > 1 then print x

Figure 7.1. Trial Division Algorithm.

One deficiency in the Fermat test is that it checks a necessary, but not sufficient,
condition: there are some composite numbers for which the above test has the same
behavior as for prime numbers, unless we pick p dividing n . For example, n

= 561 =

17 is such that for all b 's which are prime with n ,wehave b n − 1

3 · 11 · ≡ 1 (mod n ).

2 4

This can be proven easily: we notice that n − 1 = 560 = · 5 · 7 which is a multiple of

1. Therefore, if b is prime with 3, we have b n − 1 3 1 (mod 3)

and the same for 11 and 17. Hence, from the Chinese Remainder Theorem we obtain
that if b is prime with n we have b n − 1

− 1, 11 − 1, and 17 − ≡

≡

1 (mod n ). We study these numbers in more

detail in Section 7.1.2.

7.1.2 Carmichael Numbers

Theorem 7.1. We call Carmichael number any integer n which is a product of at least
two pairwise different prime numbers p such that p 1 . An integer

n is a Carmichael number if and only if it fulfills the Fermat property: for any b that is
prime with n, we have b n − 1

− 1 is a factor of n −

≡ 1 (mod n ) .

It follows that the Fermat test cannot be used in order to distinguish prime numbers
from composite ones.

=

p 1 ··· Proof. We can easily show that a Carmichael number n p r fulfills the Fermat

property: if b is prime with n , it is prime with any p i ,wehave b p i − 1

≡ 1 (mod p i ).

1 we obtain that b n − 1

Then since p i − 1 (mod p i ). Finally,

thanks to the Chinese Remainder Theorem we obtain that b n − 1

1 is a factor of n − ≡

1 (mod n ). This
means that unless we pick a b that is already a factor of some unknown prime factor
of n , the Carmichael numbers will behave just like a prime number in the Fermat
test.

≡