2
$\begingroup$

Hi

How can I generate pseudoprime numbers in a given interval without... ? - going sequentially from the smallers to the largest ones (as with a Erathostenes Sieve) - nor using slow probabilistic primality tests on a random sequence

Is there any FAST and EASY algorithm or function that generates numbers in such a way that...? - you can get small and big numbers at any given time - if you run it for a long time you get all prime numbers on that interval? (I don't mind if it also generates some composites).

I know there are some posts similar to this one but they are not the same.

regards

$\endgroup$
  • 1
    $\begingroup$ If you don't mind composites at all, you could list all numbers in your interval. The method Klyve and I used in cs.uwaterloo.ca/journals/JIS/VOL14/Klyve/klyve3.html is a lot faster but a bit harder. $\endgroup$ – François G. Dorais Mar 28 '13 at 12:46
  • $\begingroup$ Although it's hard to understand exactly what you're asking for, it seems that a probabilistic primality test would achieve what you want. Check out the Miller-Rabin primality test (on Wikipedia for example). $\endgroup$ – Greg Martin Mar 28 '13 at 16:24
2
$\begingroup$

Have you verified that the probabilistic-primality-test approach is too slow for your application? Miller-Rabin usually requires very few tests for a high level of certainty.

You might also look into libraries that provide primitives you can use. In particular, Java's BigInteger class has such methods built in. You could take a look at the method isProbablePrime(), which takes as input a certainty parameter $a$ and returns a number that is prime with "probability" (or certainty) $1 - 1/2^a$.

I wrote a test program to generate random pseudoprimes using this library (I can post the source if you are interested). The default certainty is $1 - 1/2^{100}$. Generating 100 primes of length 1024 bits takes only 20 seconds on my laptop. On the other end of the scale, generating 100,000 primes of length 40 bits takes only 20 seconds. So if you are interested in an application, it could be worthwhile to use something already available first, then plug in your own solution later if running time is an issue.

Another question (and more relevant to mathoverflow) is what sort of distribution you are looking for. I have no clue how one would go about getting a uniform distribution on primes in an interval with any decent guarantees, unless one lists all primes in the interval first and selects from it uniformly. For selecting very large (e.g. cryptographic) primes, the usual approach is to just generate a random number from the interval uniformly, then test the successive odd numbers after it until a prime is found. Because primes are so dense and the scale is quite large, this should approximate selecting a random prime from an interval quite well asymptotically. But this requires some bounds on the prime gaps, which hold in the large limit, so if you are interested in more mundane intervals (like around $10^{10}$ where it is still infeasible to list all possible primes), I don't know of any good guarantees.

$\endgroup$
1
$\begingroup$

Have a pre-determined set of small primes, say {2, 3, 5, 7, 11, 13, 17, 19}. Pick a random integer in your interval. Test for divisibility by elements of this small set. If not divisible by any, voilà.

It really depends depends on what you mean by “don't mind if it also generates some composites”. Is there a fixed maximal acceptable proportion of composites (1%, say)? If there is, that constrains the pre-chosen set.

$\endgroup$

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.