CDR: Re: StoN, Diffie-Hellman, other junk..
Asymmetric
all at biosys.net
Thu Sep 7 01:31:12 PDT 2000
-----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-----
More information about the cypherpunks-legacy
mailing list