Re: Coding opportunity with factoring problem solution with Fermat numbers
- From: mike3 <mike4ty4@xxxxxxxxx>
- Date: Tue, 17 Mar 2009 02:28:53 -0700 (PDT)
On Mar 16, 6:37 pm, JSH <jst...@xxxxxxxxx> wrote:
Two issues have emerged that I need to address. See below...
On Mar 15, 7:14 pm, JSH <jst...@xxxxxxxxx> wrote:
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
It was noticed that the algorithm will not factor a perfect square.
That's a minor issue but it needs to be stated upfront. D cannot be a
perfect square.
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).
Also note that f_1 can be negative. I've seen posters claiming
problems with the underlying algorithm where they've looped through
only positive values for f_1, and again, 1 is a potential, so also
then is f_1 = -1.
I'm going ahead and coding up a specialized implementation for
demonstration purposes as it will use long's. But with working code
maybe I can convince a few of you that there really is an opportunity
here to get the next big factorization of a Fermat number, or even
maybe find the next Fermat prime, if it exists.
So for Patricia Shanahan, yes, finally! I'll do better than pseudo-
code, as I'll do code. It will be in Java, of course.
The rub is it doesn't demonstrate for n=32... which happens to just be
outside the range of long, AND also happens to be one of those "trick"
numbers your algorithm *needs* to factor in order for it to be
anything even
remotely interesting. Can you prepare a code sample that will let me
try
n=32?
.
- Follow-Ups:
- References:
- Prev by Date: Re: Coding opportunity with factoring problem solution with Fermat numbers
- Next by Date: Re: Coding opportunity with factoring problem solution with Fermat numbers
- Previous by thread: Re: Coding opportunity with factoring problem solution with Fermat numbers
- Next by thread: Re: Coding opportunity with factoring problem solution with Fermat numbers
- Index(es):
Relevant Pages
|
Loading
