Request for example
SethKitchen opened this issue · 2 comments
Hi,
Can you show the minimum working code to factor RSA100 with this software?
Seth
That's the plan!
As the code currently stands, everything is implemented but the last part of the last step: the extraction of the algebraic square root of a polynomial over a finite field. I took about a 3 month break from the project to study abstract algebra, as clearly there was a lot that I was missing in my understanding of the reference papers. I think I have sufficient understanding now to proceed, and I realize I need to build out a fair bit more infrastructure first before the GNFS will be finished; I need to write classes for 'sparse' polynomials, multivariate polynomials, the Tonelli–Shanks algorithm for polynomials, and possibly a Chinese remainder function. Considering my other obligations at present, a (rough) estimate of how long this will take is looking to be about 2 months. Maybe 3. Also, there may be some modifications required before it can handle the number of relations needed to factor a number the size of RSA100, as I have not tested a number that big yet, but these kind of changes will be small potatos compared to hammering out the abstract algebra bit.
If worse comes to worse, and for some reason I just cannot get it working or I give up or something, the project can easily be modified to be a quadratic sieve instead. Perhaps I will do this first, just to get something out there that's working. In theory, the quadratic sieve should be sufficient to factorize RSA100. Indeed, 100 decimal digits is about the threshold point where one would want to cross over from the quadratic sieve to using the GNFS. It may take a little bit longer to do it via the quadratic sieve, but it should be well within it's capabilities.
Let me know which you would prefer: Make the project work as a quadratic sieve but at the expense of delaying the GNFS functionality a bit, or just concentrate on getting the full GNFS functionality working ASAP?
Thanks for your interest in the project!
This should be working now. I'm unsure of the exact parameters that will work best, some trial and error are neccessary. Perhaps something along the lines of (set these in you GNFS-Winforms.exe.config file):
<add key="N" value="1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139" />
<add key="Degree" value="5" />
<add key="Base" value="1261737131078349405" />
<add key="Bound" value="510379" />
<add key="RelationQuantity" value="1000" />
<add key="RelationValueRange" value="32010" />