[Hardware] Looking for people interested in factoring.

John L. Bass jbass at dmsd.com
Mon Mar 22 06:55:47 EDT 2010


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.distributed.net/pipermail/hardware/attachments/20100322/6e525874/attachment.html 


More information about the Hardware mailing list