Re: Simple answer, surrogate factoring
jstevh_at_msn.com
Date: 03/04/05
- Next message: Vladimir Bondarenko: "Maple bugs: Thomas Richard: Hurrah, Maple quality improves! - Example 4"
- Previous message: Daryl McCullough: "Re: Epistemology 201: The Science of Science"
- In reply to: Tim Peters: "Re: Simple answer, surrogate factoring"
- Next in thread: Tim Peters: "Re: Simple answer, surrogate factoring"
- Reply: Tim Peters: "Re: Simple answer, surrogate factoring"
- Reply: David C. Ullrich: "Re: Simple answer, surrogate factoring"
- Reply: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Messages sorted by: [ date ] [ thread ]
Date: 4 Mar 2005 14:49:14 -0800
Tim Peters wrote:
> [JSH]
> [...]
> > where f_1 f_2 = Tj^2, and you iterate through all possible integer
f_1
> > and f_2, and take the gcd of Ax with M.
> >
> > If Ax has M as a factor, then you calculate that ratio of z to x.
> >
> > The numerator is just
> >
> > (+/-(f_1 - f_2) + 2j^2 +/- (f_1 + f_2))
>
> I couldn't follow the derivation, so will just ask: the redundant
pair of
> outermost parentheses here is surprising, so is this really what you
meant
> to type?
>
> > while the denominator is
> >
> > 2M^2 - 2(+/-(f_1 - f_2) + 2j^2
Sorry, should be
2M^2 - 2(+/-(f_1 - f_2) + 2j^2)
>
> This one is missing a right parenthesis; don't know whether
>
> 2M^2 - 2(+/-(f_1 - f_2)) + 2j^2
>
> or
>
> 2M^2 - 2(+/-(f_1 - f_2) + 2j^2)
>
> was intended.
>
> > and you divide out any factors in common between them, and then
take
> > the gcd of the denominator with M, and for at least one case for
any
> > non-zero j coprime to M, you will have a prime factor of M.
> >
> > The basic algorithm is now perfect.
>
> I tried all plausible (to me) ways of fleshing out an implementation
from
> this, and they all failed to factor some 3-digit composites.
>
Well, the proof is actually not hard, and it is perfect, so that means
in this case I can say definitely that you made some mistake.
First off, you *will* get a factor of M, which has to be divided off,
and maybe you can get more than one factor of M, but in any event, you
have to divide off all factors of M, first.
What's left over will have a single prime factor of M for at least one
case, as the mathematical proof is in this time.
If you do it right, it will work.
James Harris
- Next message: Vladimir Bondarenko: "Maple bugs: Thomas Richard: Hurrah, Maple quality improves! - Example 4"
- Previous message: Daryl McCullough: "Re: Epistemology 201: The Science of Science"
- In reply to: Tim Peters: "Re: Simple answer, surrogate factoring"
- Next in thread: Tim Peters: "Re: Simple answer, surrogate factoring"
- Reply: Tim Peters: "Re: Simple answer, surrogate factoring"
- Reply: David C. Ullrich: "Re: Simple answer, surrogate factoring"
- Reply: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
