Wednesday, November 26, 2008


JSH: Solving for a factor

The great thing about my research into factoring is that it lets you solve for f_1 when f_1*f_2 = nT, where T is the target to be factored, and n is an integer control variable.

f_1 = ak mod p and f_2 = a^{-1}(1 + a^2)k mod p

and 'a' is related to k mod p by

a^2 = (nT)(k^2)^{-1} - 1 mod p

where p is what I call a helper prime. The equations are perfect and all issues with them come down to the issue of how fast you can use them, and with what probability you factor nT, as, of course, with mod you are looking at nT mod p.

Conventional wisdom among mathematicians has been that because given xy = r mod p, there are p-1 solutions for x and y, modular arithmetic doesn't offer the solution to solving for factorizations, but the mathematics appears to have been just slightly more subtle than they realized as of course, 'a' and k above are related by quadratic residues!!!

And in fact, it's not always possible to solve for r^2 = x mod p for any residue x, as for an odd prime there are in fact only (p-1)/2 quadratic residues, so you have an interlocking mechanism in the equation above, where k locks to particular values of 'a' through quadratic residues dependent on nT mod p, so for some values you will not have solutions, which is where the control variable n can come in, or you can pick another k.

It is remarkable that one simple additional idea could be so critical in just SOLVING for the factors of a composite: quadratic residues as key to the solution.

And just solving for one of the factors of a composite nT, has never before been done.

<< Home

This page is powered by Blogger. Isn't yours?