On Thu, 7 Sep 2000, Asymmetric wrote:
Mihailescu's methods for prime generation. (Mihailescu has a paper on the subject aimed at implementors at http://www.inf.ethz.ch/~mihailes/papers/primgen.ps )
Ah.. I have implemented a sieve of eros..whatever his name is.. ;) for
Erastothenes, I think. I don't know what a sieve of eros is. I think I'd like to try one sometime. :>
finding smaller primes.. it runs very fast, the old rules don't apply so much anymore, memory footprint being more a concern then speed I've noticed so far.. moving the found primes into a sparse array as you find them and then reusing the memory is one way around that.. even my quickly written implementation takes negligible time to find all the primes within 16 bits..
Right - I think you may find that this slows down a bit at the 500-bit range. Still, there are supposed to be ways to use sieving in conjunction with random search to speed up prime generation.
but I've been looking at rabin-miller and some other methods as well. I'll take a look at that link, thanks.. reason again for the math library.. my stuff (obviously) falls apart > 32bits since my library for handling larger numbers is unfinished.
Once you have the primitives, Rabin-Miller is straightforward to implement from the Handbook of Applied Cryptograpy. I was surprised at how easy it was... Another nice trick -- compute the product of the first 1000 primes or so. Take the GCD of this product and a candidate number. Eliminates candidates with small prime factors and often faster than trial division.
(for reasons that should be obvious) felt that writing the routines myself (with extensive testing) would be preferable, so I could avoid licensing issues as well as bugs/backdoors, but I'll look into this.. Thanks for the
Backdoors are your responsibility with GMP, so no worries, right. :). It is GPL'd, though, so be careful.
quick response.. the application will of course be available to anyone who wants it once finished.. and once Borland finishes Kylix, should compile nicely on the various x86 *nixes out there..
Looking forward to it. -David