Sunday, March 15, 2009
JSH: Factoring solution test run, Fermat primes
In case you missed it, I've found what I claim is a solution to the factoring problem involving factor D-1 in order to factor a target composite D, where I used Pell's Equation.
It was brought to my attention by Penny Hassett in a comment on my math blog that Fermat primes might be a good area to bring this new solution to bear, as factoring D-1 is then trivial.
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 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.
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 it's denominator is, 2.
Yup. 2. So like 1/2 or -1/2 will probably pop up a lot.
Ok, so one of you code jockeys can script that up and give it a whirl against Fermat numbers.
When you see that it works, break some records.
It will be screamingly fast. Like nothing you've ever seen. The records should be easily within reach, within minutes.
It was brought to my attention by Penny Hassett in a comment on my math blog that Fermat primes might be a good area to bring this new solution to bear, as factoring D-1 is then trivial.
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 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.
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 it's denominator is, 2.
Yup. 2. So like 1/2 or -1/2 will probably pop up a lot.
Ok, so one of you code jockeys can script that up and give it a whirl against Fermat numbers.
When you see that it works, break some records.
It will be screamingly fast. Like nothing you've ever seen. The records should be easily within reach, within minutes.
# posted by James Harris @ 17:26 
