I've often come across problems where (as a subproblem) I need to decide whether a list of numbers contains only primes or at least one nonprime. Is there an efficient way to do this?

Right now I tend to check all to see if they pass a probable-prime test, then use a primality-proving program on each in turn. (Nothing drastic like ECPP, just BPSW for numbers under $2^{64}$ and APR-CL for larger numbers. If the numbers are large I need specialized software to do this efficiently.)

Can this be reasonably improved? I'm actually looking for something efficient in practice (see note), so don't bring up AKS or the like.

Maybe testing for small prime factors is worthwhile -- build up a product of some small primes and take GCDs.


This question could have been asked either here or on StackOverflow; I thought that if I posted it there I would get only tweaks rather than (possibly) a better approach.

  • 1
    $\begingroup$ Is there any reason to expect that one can do better than calling the integers in turn? Are the inputs somehow related to each other? $\endgroup$ – Srivatsan Sep 9 '11 at 15:43
  • $\begingroup$ @Srivatsan Narayanan: You can do asymptotically better (on average) than proving each prime in turn by using probable-prime testing, as I mentioned. A Bernstein-type GCD tree algorithm isn't out of the question. But more generally: "can we do better?" is my whole question... if it were obvious I wouldn't have asked. $\endgroup$ – Charles Sep 9 '11 at 16:07
  • $\begingroup$ @Srivatsan Narayanan: Mine does not either. If MR denotes a probable-prime test, P a primality proof, and MRP the combination, then running MR on all inputs then P on all inputs is asymptotically faster, on average, then running MRP on all inputs. $\endgroup$ – Charles Sep 9 '11 at 16:28
  • $\begingroup$ See cr.yp.to/papers.html#sf for an example of the sort of tree algorithm I'm talking about (there are others on the same page as well as by different authors). As for the inputs, they'll often be close to each other (but too few and too large, in general, for sieving to help) and, say, log-smooth but otherwise won't have useful characteristics. I'm looking at average behavior, so they're not adversarially chosen (though if you can prove results in that model, by all means continue!). $\endgroup$ – Charles Sep 9 '11 at 16:34
  • $\begingroup$ If the numbers are fairly random, it's very likely that at least one will be an "easy" composite. So, starting with quick tests such as the gcd with 2305567963945518424753102147331756070 and progressing to the slower ones would be a reasonable approach. Try to do these "in parallel" as much as possible, allowing a quick exit if one of the numbers is found to be composite. $\endgroup$ – Robert Israel Sep 9 '11 at 18:53

In some applications one can perform the primality tests "lazily" (on demand). Even better, in some cases one can completely eliminate the primality tests by simply proceeding as if they were primes, then backing up if one later finds that there are not, e.g. if a zero divisor is encountered (Lenstra calls this a side exit from an algorithm - but the idea is much older). For example, this technique may be used while performing linear algebra computations over the "field" $\rm\:\mathbb Z/n\:.\:$ It is also used in the elliptic curve integer factorization algorithm (e.g. search for "side exit" in H. Cohen: A course in computational algebraic number theory). For another example of such techniques see D.J. Bernstein Fast ideal arithmetic via lazy localization.

Also worth stressing is that for many applications it suffices to work with coprimes rather than primes. For example, see section $4.8$ on the concept of a gcd-free basis in Bach and Shallit: Algorithmic Number Theory.

Without knowing any further details of your application, it is impossible to say if any of these techniques apply. Such techniques deserve to be much better known. They are apparently little-known outside the computational number theory community.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.