Prime Number Tests

Date: 11/12/98 at 10:50:06
From: Natalie
Subject: Prime Number

Is the number 55409243 prime?  Also, how can you test to see if a 
number is prime or not?

Date: 11/12/98 at 12:39:03
From: Doctor Rob
Subject: Re: Prime Number

No, 55409243 is not prime.

You ask a very good question about testing for primality.  There are
quite a few ways to do that.  They range from the very simple, yet
time-consuming, to the very sophisticated and quite fast.

The simplest way is to use Trial Division.  Let N be the number in
question to be tested. Divide by all prime numbers less than or equal 
to sqrt(N). If none go in evenly, then N is prime. In your case, you 
would divide by all the prime numbers less than 7443.73, of which there 
are more than 900.

Here is a slightly more complicated way. 

 1) Pick any a with 1 < a < N-1.
 2) Find the greatest common divisor d of a and N. 
    If d > 1, then N is composite, and d is a factor.  
    If d = 1, then compute the remainder of a^(N-1) when divided by N.
      If this is not 1, then N is composite.
      If this is 1, you can't tell if N is prime or not.  

Most composite numbers will be revealed to be composite by this method, 
however. This method is called the Fermat Test.

In your case, I picked a = 3, and found that a^(N-1) left a remainder
of 4483955 when divided by N, so N cannot be prime. This computation
involved 26 squarings of 8-digit numbers, 15 multiplications by 3, and 
26 divisions by N. This is slightly less work than 900-odd divisions of 
N by small primes.

Some other ways involve trying to factor the number by various 
factoring algorithms, like Trial Division above, and either succeeding 
or failing. Still other ways depend on properties of prime numbers, and 
seeing whether N does or doesn't have those properties, like the Fermat 
Test above. If it doesn't, N is not prime. If it does, you cannot be 
sure. The fastest algorithms for very large numbers are also the most 
difficult to describe and use the most sophisticated mathematics.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/