Looking for people interested in factoring.
"John L. Bass" <jbass-/[email protected]> Mon, 22 Mar 2010 04:55:47 -0600
| Newsgroups | gmane.comp.distributed-net.hardware |
|---|---|
| Message-ID | <[email protected]> |
This is a multi-part message in MIME format. --===============2684832494916000193== Content-Type: multipart/alternative; boundary="------------070306020101050108070305" This is a multi-part message in MIME format. --------------070306020101050108070305 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Hi Folks, I'm not sure this is the right place to start, but I would like to propose a d.net factoring project to knock off the remaining RSA Factoring Challenge numbers. I have an original algorithm, most similar to the rainbow tables project, where the product to be factored is decomposed into large digit partial products, that each have a corresponding precomputed set of tables, which are then combined to find the factors for the solution. In theory, after a modest set of tables are constructed for a particular size, the recombination process should run in poly time with a small exponent, and a relatively large constant. Probably not blazing fast, but likely in the weeks range for a 2048 bit RSA coprime number, assuming a lot more than a few dozen machines are available to the project. I do not have a large enough cluster, and my last attempt at this back in 2006 blew thru the available memory of my cluster and started paging badly. I did not expect that at the time, and after careful analysis, decided it was due to the nature of the data structures used, and interaction with the dynamic allocation. It was also impacted greatly by L2 cache faults, so expanding the number of processors (cluster size) is important for a reasonable run time. I have significant changes to the algorithm which need to be coded, that should mostly solve the working set problem, that are dependent on a much larger cluster than I currently have, to avoid thrashing the processor caches. I was intending to re-code using MPI/PVM, but after considering the expected size of the cluster needed, think this would be a better d.net project. I'm not sure how to restructure the algorithm into d.net work units, as there is some significant data into, and out of, each work unit ... so the project will need a several terabyte backing store, and fairly fast network connection. The algorithms constant and coefficient scaling in P can be confirmed by knocking off RSA-180, RSA-180, RSA-210, RSA-704, and if reasonable as expected, I would propose going after RSA-1024 and RSA-2048. The former, are likely to be several week projects, and the later several month projects ... but that is something of a WAG, based on how the algorithm in it's previous form solved smaller coprime problems. At the end of the day, this may resolve the "P vs. NP" problem as well. Any interest? John --------------070306020101050108070305 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1"> </head> <body text="#000000" bgcolor="#ffffff"> <font face="Fixed">Hi Folks,<br> <br> I'm not sure this is the right place to start, but I would like to propose a d.net factoring project to knock off the remaining RSA Factoring Challenge numbers.<br> <br> I have an original algorithm, most similar to the rainbow tables project, where the product to be factored is decomposed into large digit partial products, that each have a corresponding precomputed set of tables, which are then combined to find the factors for the solution.<br> <br> In theory, after a modest set of tables are constructed for a particular size, the recombination process should run in poly time with a small exponent, and a relatively large constant. Probably not blazing fast, but likely in the weeks range for a 2048 bit RSA coprime number, assuming a lot more than a few dozen machines are available to the project.<br> <br> I do not have a large enough cluster, and my last attempt at this back in 2006 blew thru the available memory of my cluster and started paging badly. I did not expect that at the time, and after careful analysis, decided it was due to the nature of the data structures used, and interaction with the dynamic allocation. It was also impacted greatly by L2 cache faults, so expanding the number of processors (cluster size) is important for a reasonable run time.<br> <br> I have significant changes to the algorithm which need to be coded, that should mostly solve the working set problem, that are dependent on a much larger cluster than I currently have, to avoid thrashing the processor caches. I was intending to re-code using MPI/PVM, but after considering the expected size of the cluster needed, think this would be a better d.net project. I'm not sure how to restructure the algorithm into d.net work units, as there is some significant data into, and out of, each work unit ... so the project will need a several terabyte backing store, and fairly fast network connection.<br> <br> The algorithms constant and coefficient scaling in P can be confirmed by knocking off RSA-180, RSA-180, RSA-210, RSA-704, and if reasonable as expected, I would propose going after RSA-1024 and RSA-2048. The former, are likely to be several week projects, and the later several month projects ... but that is something of a WAG, based on how the algorithm in it's previous form solved smaller coprime problems.<br> <br> At the end of the day, this may resolve the "P vs. NP" problem as well.<br> <br> Any interest?<br> <br> John<br> </font> </body> </html> --------------070306020101050108070305-- --===============2684832494916000193== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Hardware mailing list Hardware-Ra3b/QYEcJ3d140v2zMXi0fjHoOT/h/[email protected] http://lists.distributed.net/mailman/listinfo/hardware --===============2684832494916000193==--