The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

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

  Primality Test 

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 

  Mod, Modulus, Modular Arithmetic 

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 

  Exploring Fermat's Little Theorem 

  Large Prime Numbers 

  Primality Testing 

  Prime Number Tests 

  Testing primality of 32-bit numbers 

  Testing Prime Numbers 

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 
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.