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