CP and I are working on a way to quickly factor a large number, essentially through bruteforce/rainbow table type attack. The concept is to generate a list of prime numbers (since all composites can be evenly divided by 2 or more primes) which will reduce the search range when trying to factor a number.
We ran up to the 32-bit limit fairly quickly, which gave us over 2GB of primes (though they're not stored as efficiently as they could be). If anyone has a 64-bit computer we can play with (i.e. shell access so we can code/debug) we can go up to 2^64. But even with the right hardware, we're not sure how well this will scale, and even if it does work out well, there's the issue of hitting the 64-bit limit (which gives us 18 digit numbers).
The math in a BigInt class is horribly slow compared to built-in types; so unless we start using 128-bit CPUs, this program is essentially stuck here. However, it does very well at generating small primes. If you're interested in the details, I wrote up a paper (PDF warning) explaining in a little more detail how it works.
The source for the program is available via SVN:
https://www.diseasedmind.com/svn/genPrime/
We're working on implementing another algorithm which eliminates a lot of the math involved. Currently this alternative (genPrime_b) isn't as fast as the original, but we have an idea on how we can speed it up. That's not quite finished, but the source is also available via SVN.
Comments, suggestions, patches, and encouragement are all welcome either via e-mail, here, or on our forum http://www.dc949.org/forum
We ran up to the 32-bit limit fairly quickly, which gave us over 2GB of primes (though they're not stored as efficiently as they could be). If anyone has a 64-bit computer we can play with (i.e. shell access so we can code/debug) we can go up to 2^64. But even with the right hardware, we're not sure how well this will scale, and even if it does work out well, there's the issue of hitting the 64-bit limit (which gives us 18 digit numbers).
The math in a BigInt class is horribly slow compared to built-in types; so unless we start using 128-bit CPUs, this program is essentially stuck here. However, it does very well at generating small primes. If you're interested in the details, I wrote up a paper (PDF warning) explaining in a little more detail how it works.
The source for the program is available via SVN:
https://www.diseasedmind.com/svn/genPrime/
We're working on implementing another algorithm which eliminates a lot of the math involved. Currently this alternative (genPrime_b) isn't as fast as the original, but we have an idea on how we can speed it up. That's not quite finished, but the source is also available via SVN.
Comments, suggestions, patches, and encouragement are all welcome either via e-mail, here, or on our forum http://www.dc949.org/forum
Comment