CODEWITHSUNDEEP
algorithmsicp
Isaac Kleinman
Isaac Kleinman

Reputation: 4432

SICP, Fermat Test Issue

Section 1.2.6 of SICP describes an algorithm for Fermat prime testing as follows (my own words):

To test whether n is prime:

  1. Choose a random integer a between 1 and n-1 inclusively.
  2. If a^n %n = a, then n is probably prime.

The part I'm getting stuck on is the fact that we allow a = 1 because in this case, regardless of our choice of n (prime or not), the test will always pass.

Upvotes: 1

Views: 159

Answers (2)

IVlad
IVlad

Reputation: 43497

The text you link to actually says (emphasis mine):

Fermat's Little Theorem: If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.

(Two numbers are said to be congruent modulo n if they both have the same remainder when divided by n. The remainder of a number a when divided by n is also referred to as the remainder of a modulo n, or simply as a modulo n.)

If n is not prime, then, in general, most of the numbers a < n will not satisfy the above relation. This leads to the following algorithm for testing primality: Given a number n, pick a random number a < n and compute the remainder of a^n modulo n. If the result is not equal to a, then n is certainly not prime. If it is a, then chances are good that n is prime. Now pick another random number a and test it with the same method. If it also satisfies the equation, then we can be even more confident that n is prime. By trying more and more values of a, we can increase our confidence in the result. This algorithm is known as the Fermat test.

Up until now it never says to actually pick 1. It does later on though. I think that's a mistake, although not a big one. Even if it's true for a given value, you should test multiple values to be sure.

The pseudocode on Wikipedia uses [2, n - 1] as the range for example. You should probably use this range in practice (although the Fermat test isn't really used in practice, since Miller-Rabin is better).

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65498

You're right; there's no reason to choose a = 1. That being said, the statistical distance between the uniform distribution on [1, n-1] and the uniform distribution on [2, n-1] is O(1/n), so when n is very large (large enough that you don't just want to do trial division), the practical impact is very small (remember that this is already a probabilistic test, so a good number of other choices of a won't work either).

Upvotes: 1

Related Questions