Primality Testing

Date: 12/02/2004 at 09:09:53
From: S. Kanagaraj
Subject: Primality Testing

How can I determine if a large number given to me is prime?  Is there
a process or test I can use?  I'm writing a C program and have tried
dividing the given number by 2 or 3 and by the numbers other than 1
and itself.  But it takes so many steps in writing my program.  Is
there a faster test?

Date: 12/02/2004 at 10:37:02
From: Doctor Vogler
Subject: Re: Primality Testing

Hi S,

Thanks for writing to Dr. Math.  The next thing you have to decide is
how much math you want to learn.  Testing for primality is not an easy
thing to do, and there are numerous methods, some of which are better
for different sizes of numbers, and some of which give better results
or have better features.  For example, on our prime number page,

  Prime numbers
    http://mathforum.org/dr.math/faq/faq.prime.num.html 

there is a link to one of the simplest primality tests at

  Primality Test
    http://mathforum.org/library/drmath/view/54371.html 

This will tell you to try dividing by every number up to

  sqrt(222221) = 471.4

and you will eventually find that 222221 is divisible by 359.

A faster test, slightly more complicated but the least complicated of
the advanced tests, is the Fermat Pseudoprimality Test.  It is called
a "pseudoprimality test" because it can only tell you if a number is
NOT prime, and if it doesn't tell you that it's not prime, then it
might still be either prime or composite.  That uses modular 
arithmetic,

  Mod, Modulus, Modular Arithmetic
    http://mathforum.org/library/drmath/view/62930.html 

and is based on the fact that

  a^(p-1) = 1 (mod p)

whenever p is prime and does not divide a (this is sometimes called
Fermat's Little Theorem).  So you pick a=2 or a=3 or something similar
(and perhaps try several values) and test if

  a^(n-1) = 1 (mod n).

If it doesn't, then n cannot be prime.  If it does, then... well... n
is *probably* prime.

There are many other more complicated tests, but they get harder and
harder to understand, and harder and harder to use.  But when you have
a really, *really* big number that you want to test, you generally
need a really advanced primality test.  See also

  Determining If a Number is Prime
    http://mathforum.org/library/drmath/view/65454.html 

  Exploring Fermat's Little Theorem
    http://mathforum.org/library/drmath/view/51588.html 

  Large Prime Numbers
    http://mathforum.org/library/drmath/view/51539.html 

  Primality Testing
    http://mathforum.org/library/drmath/view/55846.html 

  Prime Number Tests
    http://mathforum.org/library/drmath/view/55884.html 

  Testing primality of 32-bit numbers
    http://mathforum.org/library/drmath/view/51512.html 

  Testing Prime Numbers
    http://mathforum.org/library/drmath/view/62917.html 

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

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