log in

Why these numbers?

Message boards : NFS Discussion : Why these numbers?
Message board moderation

To post messages, you must log in.

AuthorMessage
Profile [AF>Dell>LesDelliens]La ...

Send message
Joined: 7 Sep 09
Posts: 5
Credit: 37,812
RAC: 0
Message 23 - Posted: 8 Sep 2009, 15:40:14 UTC

Hi! I've just joined in with your project and allready User of the Day!
I was wondering about one thing: we are currently calculating on 2(big :D )numbers, but why them?? how do you choose the numbers you want to factorize? for what purpose?

Thanks

La frite
ID: 23 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Greg
Project administrator

Send message
Joined: 26 Jun 08
Posts: 640
Credit: 433,775,088
RAC: 344,736
Message 25 - Posted: 8 Sep 2009, 20:24:06 UTC - in response to Message 23.  

My interest lies in the continued development of open source, publicly available tools for large integer factorization. Over the past couple of years, the capability of open source tools, in particular the lattice sieve of the GGNFS suite and the program msieve, have dramatically improved. My collaborators and I have factored quite a few large numbers using these tools.

Integer factorization is interesting both mathematical and practical perspectives. Mathematically, for instance, the calculation of multiplicative functions in number theory for a particular number require the factors of the number. Likewise, the integer factorization of particular numbers can aid in the proof that an associated number is prime. Practically, many public key algorithms, including the RSA algorithm, rely on the fact that the publicly available modulus cannot be factored. If it is factored, the private key can be easily calculated. Until quite recently, RSA-512, which uses a 512-bit modulus (155 digits), was used. As recently demonstrated by factoring the Texas Instruments calculator keys, these are no longer secure.

For most recent large factorizations, the work has been done primarily by large clusters at universities. There are two other public efforts, NFSNet and MersenneForum, in both of which I have participated, but the software used by NFSNet doesn't incorporate the latest developments and participation in the MersenneForum effort requires manual reservation and submission of work. I have been toying with the idea of trying a BOINC project for a while now to make it easy for the public to participate in state-of-the-art factorizations, and I found the time to do so. My interest in this project is to see how far we can push the envelope and perhaps become competitive with the larger university projects running on clusters, and perhaps even collaborating on a really large factorization.

The numbers are chosen from the Cunningham project. The project is named after Allan Joseph Champneys Cunningham, who published the first version of the factor tables together with Herbert J. Woodall in 1925. This project is one of the oldest continuously ongoing projects in computational number theory, and is currently maintained by Sam Wagstaff at Purdue University. The third edition of the book, published by the American Mathematical Society in 2002, is available as a free download. All results obtained since the publication of the third edition are available on the Cunningham project website.

Concerning target size, I started out somewhat "small" (small meaning that I can do it on our cluster in a few days), but it also took the contributors to this project only a few days as well. For our second project, I chose a target somewhat larger. I will continue to slowly increase the size. The real limit is the memory requirement. The current project requires a bit less than 512 MB of memory. As the size of the target increases, that will also increase somewhat. I will be keeping a close eye on that as we move forward.
ID: 25 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile [AF>Dell>LesDelliens]La ...

Send message
Joined: 7 Sep 09
Posts: 5
Credit: 37,812
RAC: 0
Message 27 - Posted: 9 Sep 2009, 18:38:38 UTC

Thanks a lot for this complete answer!

I also posted your answer on the forum of my team "L'Alliance Francophone" to share those interesting news ;)

La frite
ID: 27 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote

Message boards : NFS Discussion : Why these numbers?


Home | My Account | Message Boards