Small prime test divisor efficiency strategy

[fenderbender]

I'm coding my own c++ library of number theory routines (because it's the best way to learn!).

I am now working on a general "is this number prime?" routine.
My basic strategy is trial division for the first (few hundred?)
primes, then a-pseudoprime tests for a=2,3,5, etc.
If I get really ambitous I'll implement the Ballie-PSW test.

My question is a general efficiency one. For testing the list of the first few hundred primes, is it generally faster to do trial divisions of each divisor sequentially, or to do a GCD with the product of many primes at once?
I am sure the exact balance depends on implementation efficiency of divides and GCD, but I would expect that for testing hundreds of divisors, you'd end up using the GCD to do many in parallel.
But online code (for example the clean presentation by Thomas Nicely) uses explicit division for each of the the first 6000+ primes, not GCD.

I have only penciled in the rough guess of computational efficiency but surely a GCD of many primes at once will take far fewer operations (admittedly using larger numbers) than explicit divides.

Or maybe the "early abort" of individual tests is efficient.. once you find a divisor, you don't really care about any others, you know it's not prime.

Thanks for any advice!

[R.D. Silverman]

Originally Posted by fenderbender

I'm coding my own c++ library of number theory routines (because it's the best way to learn!).

I am now working on a general "is this number prime?" routine.
My basic strategy is trial division for the first (few hundred?)
primes, then a-pseudoprime tests for a=2,3,5, etc.
If I get really ambitous I'll implement the Ballie-PSW test.

My question is a general efficiency one. For testing the list of the first few hundred primes, is it generally faster to do trial divisions of each divisor sequentially, or to do a GCD with the product of many primes at once?
I am sure the exact balance depends on implementation efficiency of divides and GCD, but I would expect that for testing hundreds of divisors, you'd end up using the GCD to do many in parallel.
But online code (for example the clean presentation by Thomas Nicely) uses explicit division for each of the the first 6000+ primes, not GCD.

I have only penciled in the rough guess of computational efficiency but surely a GCD of many primes at once will take far fewer operations (admittedly using larger numbers) than explicit divides.

Or maybe the "early abort" of individual tests is efficient.. once you find a divisor, you don't really care about any others, you know it's not prime.

Thanks for any advice!

A GCD of (N, Prod p_i, i < k) should be faster than trial dividing the
primes up to p_k, but (as you point out), whether it is faster in practice depends on HOW LIKELY it is that N is prime. Trial division aborts after
a divisor is found, so you may not do most of the divisions. If N is drawn
truly uniformly at random from some interval, then trial division should be
faster on average. If you have some prior expectation that N might be prime
(for whatever reason), the GCD's will probably be faster.

However, you are optimizing something that only takes microseconds
anyway.

[fenderbender]

Originally Posted by R.D. Silverman

If N is drawn
truly uniformly at random from some interval, then trial division should be
faster on average. If you have some prior expectation that N might be prime
(for whatever reason), the GCD's will probably be faster.

However, you are optimizing something that only takes microseconds
anyway.

That's a good point, context really matters, since depending on application, you may truly expect a prime with only rare exceptions, or have random numbers which will likely be composite. It's almost worth making two routines.

You're also right that actual evaluation is microseconds, but in my mind this may be something that could be repeated bilions or trillions of times, so it's elegant to get it efficient. [That kind of elegant optimization is the bane, and the joy, of perfectionist programmers.]

Thanks!

[R.D. Silverman]

Originally Posted by fenderbender

That's a good point, context really matters, since depending on application, you may truly expect a prime with only rare exceptions, or have random numbers which will likely be composite. It's almost worth making two routines.

You're also right that actual evaluation is microseconds, but in my mind this may be something that could be repeated bilions or trillions of times, so it's elegant to get it efficient. [That kind of elegant optimization is the bane, and the joy, of perfectionist programmers.]

Thanks!

What application might try to test primality of "billions" or "trillions" of numbers
by trial division?

[fenderbender]

Originally Posted by R.D. Silverman

What application might try to test primality of "billions" or "trillions" of numbers
by trial division?

That.... is a very very good question... and one that I hadn't clearly thought about! I am so "new" to the game I am just building up some fundamental routines and hadn't thought how they might be used.

The only answer to a billions-of-isPrime tests is probably some naive algorithm such as doing trial divisions for (lots) of small primes, and the routine would use the prime test to come up with those trial divisors. But that's a pretty inelegant algorithm.. it'd be fine for hundreds or even a million imes, but a billion.. ?

Heh, thanks for making me think about the importance of what routines need speed and which don't. Your simple reply made me think about that more.

[bsquared]

If you are new, and looking for routines/algorithms to learn about and implement, one that is relevant to finding primes in a (possibly very large) list of numbers is a sieve.

The sieve of Eratosthenes is simple, and quite well known. However, really efficient versions involve some sophisticated coding, knowledge of the computer architecture, and some number theory to boot. It is a great algorithm for people that like to tinker/optimize. Here are a couple good sites that descibe efficient versions of the algorithm.

http://www.ieeta.pt/~tos/software/prime_sieve.html
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html

- ben.