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
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

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

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search