Sunday, March 15, 2009


Coding opportunity with factoring problem solution with Fermat numbers

I've solved the factoring problem, which took a lot of effort. Now the new method that solves the factoring problem is rather easy in a lot of ways, but also it is almost perfect for factoring Fermat numbers, and can, if one exists, find the next Fermat prime.

That opens the door to a remarkable, earthshaking result for anyone willing to do a little code work.

The possibility here is in finding the next Fermat prime.

Here is the factoring algorithm:

Given an odd composite D, to be factored, you factor it by taking its gcd with a function I call r_c(v), where:

r_c(v) = 2((D+1)v^2 - 2f_1*v + f_1^2)

and f_1 is a factor of D-1, so with Fermat numbers, it is always just 1 or 2 raised to some natural number power, where you find rational v, such that v is in the following range:

(f_1 - sqrt(f_1^2 - [f_1^2 - D/2](D+1)))/(D+1) < v < (f_1 + sqrt(f_1^2 - [f_1^2 - D/2](D+1)))/(D+1)

and r_c(v) is an integer, where if that range gives an integer v, then you're done, as you just plug that into r_c(v), and you're guaranteed have a factorization of D, from the gcd with r_c(v).

Notice for rational range f_1 <= sqrt(D/2).

If no integers are available for v, not to worry! Turns out a rational solution MUST exist if there is rational range at all, and its denominator is, 2.

Yup. 2. So like 1/2 or -1/2 will probably pop up a lot.

There is a mathematical proof that the method I just gave you WILL give each non-trivial factorization of D, if any exist, so if none pop up, D is prime.

It is screamingly fast because notice, for D = 2^2048 + 1, you have 2049 iterations to give each possible f_1.

So this method is most optimal for Fermat numbers, and may be the only hope for finding another Fermat prime if one exists.

Even if one does not, you can get a record for the largest Fermat number factored, easily enough.

<< Home

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