3 ms·
about 12 years ago I came up with a pretty clever way to factor numbers that I never pursued the computational complexity of. The basic algorithm is that you t
by kristopolous 11y ago
about 12 years ago I came up with a pretty clever way to factor numbers that I never pursued the computational complexity of.
The basic algorithm is that you take some candidate X (which will be our 2048 bit number here) and classify your question (primality, whether it is the product of 2 primes, etc) --- once you have your question, Q, then you can pick a number Y0 to get X % Y0 = Z0 ... sometimes ~sqrt(X) works well, other times it's the closest prime factorial, etc.
now using those results, [Q, Y0, Z0], you can optimally pick Y1 and do the operation again, X % Y1 = Y2 ...
Like the Chinese remainder theorem each Z gives you information on the next optimum Y given your question Q ...
I called it tunnel factoring and saw some great early results ... but for some reason I haven't ever pursued it
- chadnickbok 11y agoGood engineers ship.
- deleted 11y ago[deleted]
- kristopolous 11y agoDo you actually want the source? It's similar to gnfs, but my implementation of my algorithm seems to be faster in c, under probably gcc 2.95 when compared to a reference gnfs i had found online ... enough times to be significant (but a result of "faster on my computer" doesn't really lead to any kind of "breaking news"). It could just be due to an ineffecient implementation. I'll have to look at some old cvs repos ... Hopefully I can find it. I'll put it on guthub if i can. I worked a good 6 months on it and I understand the gravity of the claim. I have no interest in being bogus or fraudulent.
- sillysaurus3 11y agoHopefully I can find it. I'll put it on guthub if i can. Please do. It sounds very interesting.
- chadnickbok 11y agoYes, please do put it on GitHub! It does sound like a big claim, but what do you have to lose? I'm personally trying to get more of my projects out into the open, even before I feel like they're ready - having code I put lots of time into that never gets seen by anyone makes me feel like I'm wasting my time. But at least getting some feedback helps me build better things next time.