CDR: Re: StoN, Diffie-Hellman, other junk..
dmolnar
dmolnar at hcs.harvard.edu
Wed Sep 6 23:07:37 PDT 2000
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
More information about the cypherpunks-legacy
mailing list