[Hardware] Looking for people interested in factoring.
Martin K
martin at nnytech.net
Mon Mar 22 20:12:58 EDT 2010
John L. Bass wrote:
> 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 recode 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 RSA180, RSA180, RSA210, RSA704, and if reasonable as
> expected, I would propose going after RSA1024 and RSA2048. 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
>
John,
I'm interested in helping. I'm a bit more of a hardware and lowlevel
'expert' rather than a computer scientist. I also have no involvement
with d.net if that's what you're looking for specifically. I am,
however; looking for a project to work on that isn't writing 8 bit
assembly code or dealing with ultrasonic communication.
If you have something I can read up on, let me know.

Martin K
More information about the Hardware
mailing list