CDR: Re: StoN, Diffie-Hellman, other junk..

[Asymmetric]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

At 02:07 09/07/2000 -0400, dmolnar wrote:

>Erastothenes, I think.
>I don't know what a sieve of eros is. I think I'd like to try one
>sometime. :>

Hah yeah that spelling looks right.. it's really pretty elegant, and was 
considered at the time of the writing of AC 2nd ed. to be faster for 
numbers of 100 digits or less.. since a base-10 digit is roughly 3.5 bits, 
that should be faster than say the general number sieve for numbers up to 
about 350 bits.

It works by first making an array of bits, all set to true, that represent 
all the numbers from 2 - X, where X is the last number you want to test for 
primeness.  You loop through the array from begining to end.. for each bit 
you find set, you set all multiples of that number up to X off.  This 
results in every multiple of every prime (which is to say, every composite 
number) being marked "false" in the array.  When finished, you have an 
array of bits where an on bit represents a prime.  The storage issue 
results because I currently store an array of bytes instead of an array of 
bits.. so to test the first ~ 16 million numbers (24 bits) requires about 
16 meg of storage.  That would drop to 2 meg if I rewrote it to be a 
bit-array, which I intend to do.. and it would only take N bytes of memory 
if instead implemented as a sparse array of bytes, where N = the number of 
primes from start to finish of your range.


>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.

Probably would slow down some around 512bits.. which should represent 
numbers about 147 base-10 digits.


>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...

I expect it'll be easier when I look at it again.. it still looks a bit 
messy though.  AC 2nd ed describes rabin-miller as follows, p260, pp2..

(p = prime)

1. Calculate b, where b is the number of times that 2 divides into p - 1.
2. Calculate m, such that p = 1 + 2^b * m.
3. Choose a random number "a" such that "a" is less than "p".
4. Set j = 0 and set z = a^m mod p.
5. if z = 1, or z = p - 1, then p passes and may be prime.
6. if j > 0 and z = 1, then p is not prime.
7. set j = j + 1.  If j < b and z != p - 1, set z = z^2 mod p, and go back 
to 6.  If z = p - 1, then p passes the test and may be prime.
8. If j = b, and z != p - 1, then p is not prime.

I think I need to just be a bit less tired before I can parse that 
efficiently into code.. :)


>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.

Do you mean calculate each product of two of the first 1000 primes?  (i.e. 
2*3, 2*5, 2*7... 5*7...) etc? for each possible pair?


>Backdoors are your responsibility with GMP, so no worries, right. :). It
>is GPL'd, though, so be careful.

Yeah.. hadn't decided if I was going to open source it or not.. but I 
suppose putting it under the GPL myself does prevent anyone else from 
making money off my work.. ;)  I'm not looking to make any money from this 
product, but I certainly don't want anyone else making money off my hard 
work either.  I need to read the GPL or GLPL closely.. whichever GMP is under.


>Looking forward to it.

Cool.. thanks for the help and links again.. tried to sleep for the past 
two or three hours, couldn't.. I'm back up and at it. ;)


- -------signature file-------

"'There comes a time when the operation of the machine
becomes so odious, makes you so sick at heart, that you
can't take part; you can't even passively take part, and
you've got to put your bodies upon the gears and upon the
wheels, upon the levers, upon all the apparatus, and you've
got to make it stop. And you've got to indicate to the people
who run it, to the people who own it, that unless you're free,
the machine will be prevented from working at all!"
- -Mario Savio-  Founder of the Free Speech Movement.

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

iQA/AwUBObdSUGvp1znMxX/XEQKL+wCghGPE649K/LKbWFqyiVU9EeRDVywAn2JA
LAtFdc1JFEEo4YiRcMzrE8L+
=IMRU
-----END PGP SIGNATURE-----