Thursday, November 27, 2008


Solving directly for factors of a composite

I've found that you can solve directly for f_1 and f_2 when f_1*f_2 = T, where T is a composite to be factored:

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 = (T)(k^2)^{-1} - 1 mod p

where p is what I call a helper prime.

To get the direct solution you pick p a prime where p>sqrt(T) and pick for k a positive integer near p.

Example: Let T=119. Then p=11 is greater than sqrt(119), and trying k=10 gives

a^2 = (119)(10^2)^{-1} - 1 mod 11 = 8 mod 11,

but 8 is not a quadratic residue modulo 11, so no 'a' exists for this case. Trying now k=9, gives

a^2 = (119)(9^2)^{-1} - 1 mod 11 = 4 mod 11

so a=2 is a solution. And ak = 18, which is greater than 11, so

f_1 = ak = 18 mod 11 = 7 mod 11.

And you have a non-trivial factorization, as 7 is a factor of 119.

It's an oddly simple method given the history in this area. I'm popularizing it in the hopes that eventually I can get the mathematical community to acknowledge this surprising result.

They missed it, and with something simple unfortunately modern mathematicians are the hardest to convince as they believe everything simple has already been discovered, and they don't believe you can solve directly for factors using congruence relationships.

But the simple mathematics above proves that conventional wisdom in this area has been wrong.

<< Home

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