Saturday, November 29, 2008


JSH: Wow, maybe factoring algorithm DOES work!

Those who know how I use the newsgroups know that I like to put out early research results to help in critiquing them. It speeds things up. For years I've worked at finding a new way to factor with so many failed approaches that I have often been nearly at my own limit, so more so than with other research I just toss things out there.

But not only hasn't anyone come back to show this approach really works badly I replied a few minutes ago to a poster who may have worked at finding a picked example with a rare case where things don't work with the basic algorithm!!! Cool. Maybe the damn thing DOES work then as it looks like he worked for a while to try and find an example where it didn't!

Here's the algorithm, as a re-cap, and then I'll talk some more about what these last few days of posting may mean:

Simply enough I found that you can solve for f_1 and f_2 when

f_1*f_2 = nT,

where T is some target composite to be factored and n is a non-zero integer control variable, modulo some prime number p, where

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.

You pick a prime p greater than sqrt(T), and pick a positive integer k, as close to p as you can get, like k=p-1, and then try to solve for 'a', and if you can, and also ak is greater than p, then you will have factored nT mod p, with high likelihood you factored nT itself.

Here's my pet example again to demonstrate:

Example: Let T=119. Then p=11 is greater than sqrt(119), and trying k=10, with n=1 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.

If that works for small numbers it should work for big numbers as there's a scaling built-in which I talk about which has to do with a number called k_0 and floor(k_0/2p) so it could be a REALLY big deal if all that is actually working because it's also polynomial time. The gist of it is that the bigger the number the bigger the prime p that you choose, and that's it. Automatically scales everything for you.

Folks, if the last few days of posting are an indicator then I may have found the world's first polynomial time factoring algorithm!

It could be a remarkable discovery where there will be no debate, no arguing, and no questions about whether or not mathematicians can decide if it's of interest or not.

My hope is that math people who have argued with me for years will show maturity in this situation, and simply congratulate me on a hard victory, which took years to accomplish, and enjoy the wonder of a simple answer where no one thought one could be.

Indications are growing that the world has its first polynomial time factoring algorithm. Wow.

<< Home

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