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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.