Drexel dragonThe Math ForumDonate to the Math Forum

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

Testing primality of 32-bit numbers


Date: 18 Nov 94 23:21:00 GMT 
From: Anonymous
Subject: testing primality of 32-bit numbers

Dear Dr. Math,

What is the best (fastest) way to test if an arbitrary 32-bit
number is prime?

Dividing by all numbers up to the square root is not great since
you need to build a table of primes.  I am using a test that checks
if the number is a string pseudo prime to bases 2, 3, and 5 which
is pretty good.  But is there are better way?

Thanks,
Brian Beuning

P.S.  If this isn't the type of question you handle, that's fine.


Date: Fri, 18 Nov 1994 20:15:32 -0500 (EST)
From: Dr. Ken
Subject: Re: testing primality of 32-bit numbers

Hello there!

Yes, there is a faster way.  I'll assume that you're familiar with modulo
arithmetic, since you wrote about strong pseudoprimes.  If this isn't the
case, let us know.

The better way is called the Lucas Test for Primality.  It does rely on
factoring, but not of the number in question.  If you're trying to determine
whether the number M is prime, you have to factor M-1.  This isn't usually
very hard, since it's certainly even if you're testing M for primality, and
in general you'll get lots of small factors for a big number.  Anyway,
here's how you apply the test:

You find all the prime factors p1, p2, p3, ..., pk that divide M-1.  You
don't really need to know how many powers of each prime go into M-1, just
which primes.  Then you pick a number (call it A) that's less than M.  
Raise A to the power M-1, and find what it's congruent to Mod M.  If it's
not congruent to 1, then M isn't even a pseudoprime (which is different than
a strong pseudoprime) to the base A, so it's composite.  If A^(M-1) is
congruent to 1 Mod M, then continue.

Raise A to the power (M-1)/p1, and find what it's congruent to Mod M.

***Note: do you have an efficent way to raise numbers to big powers when
you're doing modulo arithmetic?  The number of steps you can do it in is
about Log of the number of digits in the power.  It's done most efficently by
the method of successive squares.***

If it's congruent to 1, pick a new A and try again.  If it's not, then find
A^((M-1)/p2) (Mod M).  Keep going like this with all the different primes
that divide M-1.  What you want is for there to be a number A for which none
of these power-raisings is congruent to 1 Mod M.  Stated precisely, here's
the theorem:

If there is an A such that A^(M-1) == 1 (Mod M), and for every p dividing
M-1   A^((M-1)/p) =/= 1  (Mod M),  then M is prime.

That first set of equal signs means "is congruent to", and the second set
means "is not congruent to."

Note that this gives an airtight proof of the primality of a number.  It's a
little slower then finding out whether M is a strong pseudoprime to every
base, which is what you'd really have to do to really show that your number
is really a prime, and not just some imposter.  But you know, it's really a
pretty good test to check the first few bases for pseudoprimes, and here's
why.

If you find that M is a strong pseudoprime to the base 2 and M is smaller
than 2047, then M is prime.  If you test it again with the base 3, and it's
again a strong pseudoprime, then M is a prime provided it's less than
1373,653.  If you test it again to the base 5, and it's again a strong
pseudoprime, then M is prime provided it's less than 25,326,001.  That's the
smallest number that's a SSP to the base 2,3, & 5.  So odds are pretty good
that if it tests out to all three bases, it's a prime.  Of course, it's a
gamble.....

I hope that helps.

Well, it's not really the kind of question we deal with usually (i.e. a
question from a k-12 student), but I'm happy to give it a shot.

-Ken "Dr." Math
    
Associated Topics:
College 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-2013 The Math Forum
http://mathforum.org/dr.math/