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