Re: I was right, surrogate factoring proof
jstevh_at_msn.com
Date: 02/14/05
- Next message: Nora Baron: "Re: Surrogate factoring, room for error?"
- Previous message: jstevh_at_msn.com: "Re: My brainstorming and crank label"
- In reply to: Tim Peters: "Re: I was right, surrogate factoring proof"
- Next in thread: jstevh_at_msn.com: "Re: I was right, surrogate factoring proof"
- Reply: jstevh_at_msn.com: "Re: I was right, surrogate factoring proof"
- Reply: Tim Peters: "Re: I was right, surrogate factoring proof"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 13 Feb 2005 16:35:21 -0800
Tim Peters wrote:
> [JSH]
> > Ok. An algorithm is easy.
>
> BTW, thank you for posting this! You can believe it's because I'm
stupid if
> you want to, but I never would have guessed that this is the
algorithm you
> had in mind based on your list of equations.
I don't have a negative opinion on the subject.
Believe it or not, I'm just trying to figure some things out.
I don't have a lot of personal interest in most of you, one way or
another.
>
> > Given an odd natural number M to be factored.
>
> As it seems to have turned out later, M can't be a square (although
the
> algorithm actually works for M=9).
>
That's an interesting tidbit. I'll have to think about it later.
If it did work for that case, it's a special case, possibly having to
do with...I don't know why it would work.
I'd have to think about it, but if it did work, that's a special case.
> > Select j. Simplest is to let j = floor(M/2).
> >
> > If j is even, add 1.
> >
> > Calculate T.
> >
> > T = M^2 - j^2.
> >
> > Factor T, and j.
> >
> > Iterate through integer f_1 and f_2 such that f_1 f_2 = Tj^2.
>
> This part wasn't entirely clear. Is there an implicit assumption
that f1>1
> and f2>1? Just because it wasn't clear, in most of the results I
reported I
> used _all_ integer f_1 and f_2 whose product was Tj^2. For example,
if Tj^2
> factored to 2*3 (which no Tj^2 could factor to, but I just want to
keep this
> list small), I tried these 8 possibilites for f_1 and f_2:
>
> f_1 f_2
> 2 3
> 3 2
> -2 -3
> -3 -2
> 1 6
> 6 1
> -1 -6
> -6 -1
>
> I doubt that's what you intended, but since it wasn't clear I tried
to use
> the union of everything that might have been intended.
You need to get every possible integer Ax, so whatever does that should
be done.
Some of those I'd think would necessarily give the same answers though.
Doesn't hurt, but would just be a waste. You just need every distinct
Ax.
> > For each f_1 and f_2 calculate Ax using
> >
> > Ax = (f_1 - f_2) + 2j^2
> >
> > and
> >
> > Ax = (f_2 - f_1) + 2j^2
> >
> > to handle plus or minus, and take the gcd of Ax with M.
> >
> > The gcd of Ax with M will be a single prime factor of M, for at
least
> > one set of f_1 and f_2.
>
> All of that was clear.
It seems right to me, so I don't know why it wouldn't work.
The math seems straightforward but if it doesn't work then something is
wrong somewhere, either in the theory or implementations.
I'm more of a theory guy, like I'm a theoretical amateur mathematician.
Sure, I can code and test, but I kind of do it as a last resort,
preferring to work it all out theoretically first to see what MUST be
true.
James Harris
- Next message: Nora Baron: "Re: Surrogate factoring, room for error?"
- Previous message: jstevh_at_msn.com: "Re: My brainstorming and crank label"
- In reply to: Tim Peters: "Re: I was right, surrogate factoring proof"
- Next in thread: jstevh_at_msn.com: "Re: I was right, surrogate factoring proof"
- Reply: jstevh_at_msn.com: "Re: I was right, surrogate factoring proof"
- Reply: Tim Peters: "Re: I was right, surrogate factoring proof"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
