Wednesday, August 22, 2007
JSH: Surrogate factoring analysis, done?
After my failure with what I deluded myself into thinking (for a while) was the perfect factoring algorithm, I just bit the bullet and began the detailed and tedious analysis that my latest insight indicated which took me into the calculus which was kind of fun, and a bit surprising, and now it looks to me like if I didn't screw up the analysis is done.
Remember what I call surrogate factoring is an integer factorization technique that involves factoring some other number than your target to in fact factor your target composite, which is a lateral thinking kind of move.
I have a complete page at my Extreme Mathematics group:
http://groups.google.com/group/extrememathematics/web/integer-factorization
Or you can go to my math blog.
For those who'd like a synopsis or a teaser, whatever you might like to call it, the key result is that the method works within certain limits, where the key limits is:
-(k+2xT)/T < m < -(k + 2xp)/T
where p is a prime factor of your target T, and m is less important than the range, as
floor(-(k + 2xp)/T - (-(k+2xT)/T))
is the exact count (assuming I did my analysis correctly!!!) of possible solutions that will non-trivially factor with the smallest absolute value of the surrogate, where with a congruence of squares
x^2 = y^2 mod T
you have that both x+y and x-y share prime factors with T.
If only ONE of them does then the limit shifts to
-(k+2xp)/ < m < -(k + 2x)/p
as the range that gives the total number of non-trivial solutions that will factor out one prime only, and practically that is what you get most of the time, with the smallest prime getting yanked out, so my analysis explains the why of it all.
So now it makes sense when and why the surrogate factoring equations work.
Lots more detail in the complete analysis than I expected so I'd appreciate any comments noting errors in that analysis.
I am rather excited by this analysis as it was back in August of LAST YEAR that I finally boiled down the surrogate factoring concept to some simple key equations and I've puzzled over how and why they work—or do not—since then, off and on.
Now finally I think I have the answers, and know the 'why' of surrogate factoring.
Looking for critiques! Especially anyone noticing mistakes!!!
http://groups.google.com/group/extrememathematics/web/integer-factorization
You can check it all out there. I like to think I'm clever but did I get the calculus right?
I AM an amateur playing at it so this is on topic for alt.math.recreational, and remember the issue has not been about whether or not the surrogate factoring can work, but whether or not it can be a viable factoring technique which required the kind of detailed and in-depth analysis that I think I've completed.
And it took about a year, not that I was working at it full time, but for those looking to do any kind of big research, expect years of effort. YEARS!!!
It will take you years if you have any ideas that might actually pan out.
Remember what I call surrogate factoring is an integer factorization technique that involves factoring some other number than your target to in fact factor your target composite, which is a lateral thinking kind of move.
I have a complete page at my Extreme Mathematics group:
http://groups.google.com/group/extrememathematics/web/integer-factorization
Or you can go to my math blog.
For those who'd like a synopsis or a teaser, whatever you might like to call it, the key result is that the method works within certain limits, where the key limits is:
-(k+2xT)/T < m < -(k + 2xp)/T
where p is a prime factor of your target T, and m is less important than the range, as
floor(-(k + 2xp)/T - (-(k+2xT)/T))
is the exact count (assuming I did my analysis correctly!!!) of possible solutions that will non-trivially factor with the smallest absolute value of the surrogate, where with a congruence of squares
x^2 = y^2 mod T
you have that both x+y and x-y share prime factors with T.
If only ONE of them does then the limit shifts to
-(k+2xp)/ < m < -(k + 2x)/p
as the range that gives the total number of non-trivial solutions that will factor out one prime only, and practically that is what you get most of the time, with the smallest prime getting yanked out, so my analysis explains the why of it all.
So now it makes sense when and why the surrogate factoring equations work.
Lots more detail in the complete analysis than I expected so I'd appreciate any comments noting errors in that analysis.
I am rather excited by this analysis as it was back in August of LAST YEAR that I finally boiled down the surrogate factoring concept to some simple key equations and I've puzzled over how and why they work—or do not—since then, off and on.
Now finally I think I have the answers, and know the 'why' of surrogate factoring.
Looking for critiques! Especially anyone noticing mistakes!!!
http://groups.google.com/group/extrememathematics/web/integer-factorization
You can check it all out there. I like to think I'm clever but did I get the calculus right?
I AM an amateur playing at it so this is on topic for alt.math.recreational, and remember the issue has not been about whether or not the surrogate factoring can work, but whether or not it can be a viable factoring technique which required the kind of detailed and in-depth analysis that I think I've completed.
And it took about a year, not that I was working at it full time, but for those looking to do any kind of big research, expect years of effort. YEARS!!!
It will take you years if you have any ideas that might actually pan out.
# posted by James Harris @ 20:27 
