Re: Surrogate factoring, more theory

jstevh_at_msn.com
Date: 02/08/05 

Date: 8 Feb 2005 04:22:17 -0800

Thanks.

Décio Luiz Gazzoni Filho wrote:
> Rick Decker wrote:
> > <huge snip>
> >
> > What James appears to be doing here is looking at the discriminant
> > of his expression for z, namely
> >
> > (Ax - 2j^2)^2 + 4Tj^2
> >
> > [I'm pretty sure he's made a sign error here, which I've corrected.
> > It doesn't matter in any case.]

Oh, maybe I did. That might explain things. Well I've always had
problems with sign errors.

> >
> > Now this discriminant must be a rational square, say r^2, so we
> > have
> >
> > (Ax - 2j^2)^2 + 4j^2T = r^2
> >
> > so
> >
> > (Ax - 2j^2)^2 - r^2 = -4Tj^2
> >
> > and we observe that the LHS is the difference of two squares, so
> > we factor -4Tj^2 (in integers?) as w_1 w_2, from which we have
> >
> > [(Ax - 2j^2) + r][(Ax - 2j^2) - r] = w_1 w_2
> >
> > and a little manipulation gives
> >
> > x = (w_1 + w_2 + 4j^2) / (2A)
> >
> > as a "factor" of M^2. Then it seems as if James looks at the
> > numerator of x for factors in common with M.
> >
> > There are a few problems with this approach. First, some
factorizations
> > {w_1, w_2} don't yield any useful factors of M. Even more
troubling
> > is the fact that in order to factor M by this method, we have to
> > factor -4Tj^2 = -4(M^2 - j^2)j^2 = -4(M + j)(M - j)j^2, which
appears
> > to be at least as difficult to factor as M itself (especially if
one
> > uses this method recursively).
>
> If one can pick j at will (and easily switch from one value to
another),
> then this bears a small resemblance to the elliptic curve method: use
a
> little computational power with each curve, and if it fails, try
another,
> since it's so easy to switch from one the other. Figure out an
optimal
> balance between computational power applied to each curve and
probability
> that a given curve is successful in factoring the integer in
question, and
> you're done.
>
> Assuming no restrictions are placed on j, then it would be easy to
find j
> such that M + j and M - j are easily factorable. In fact, using an
> heuristic similar to the twin prime conjecture, one could argue that
M + j
> and M - j are both prime (and thus trivially factorable) with
probability
> O(1/log^2 M). Thus we expect to look at O(log^2 M) values of j before
a
> suitable value is found. A pseudoprimality test costs O(log^3 M)
assuming
> grammar school multiplication, so O(log^5 M) operations. Certifying
this
> prime with fastECPP is an O(log^5 M) task assuming grammar school
> multiplication, so indeed James' algorithm would be polynomial time.
The
> question is, can the remaining holes be filled? I don't think so.

Wow! Neat. Thanks. I was certain it was polynomial time.

>
> Sorry to feed the troll, but as James repeatedly proclaims, you can't
argue
> with the mathematics.
>

Well, sci.math'ers can, which can be seen by the "Nora Baron" post
earlier in the thread.

Now you people may hate me, and God knows I've said quite a few odd
things over the years, but at some point I hope you just like
mathematics enough to pay attention to the math.

Basically I have discovered a way to factor that involves using factors
of a surrogate which counteracts the idea of finding hard primes by
pushing the factorization to some other number.

That in and of itself should get your attention.

And, I've worked out the theory enough to see that actually the
factorization of T is all you need, though then you have to deal with
factors of 2, to balance out

yx^2 + Ax - M^2 = 0

so, I was wrong to say that A has no impact, as in fact you, um, need A
to be even, like A = 2^{2n}), where n is a natural.

But hey, I've working out the theory, figuring this out as I go!!!

So, yes, I was wrong. The value of A does matter somewhat, but only to
balance out evens and odds.

James Harris

Relevant Pages

  • Re: What puzzles me, discovery ignored
    ... Does James actually have a general solution, ... factorization, but have solutions. ... Factorization, 2 variable diophantine equations, Pell ... The following two transform pairs on and ...
    (sci.math)
  • Re: What puzzles me, discovery ignored
    ... I got one from James, ... No. James' factorization method relates to forms like: ... Factorization, 2 variable diophantine equations, Pell ... The following two transform pairs on and ...
    (sci.math)
  • Re: What puzzles me, discovery ignored
    ... Does James actually have a general solution, ... I found a way to convert them to the Pell - like ... factorization, but have solutions. ... The following two transform pairs on and ...
    (sci.math)
  • Re: What puzzles me, discovery ignored
    ... Common Divisor function GCDworking - can't remember if GCD ... Does James actually have a general solution, ... factorization, but have solutions. ... transforms with any integer value of v, ...
    (sci.math)
  • Re: Beginner Gear Advice
    ... I sail on Pymatuning Lake on the Ohio/Pa border. ... the lake house is Erie, ... (Kurt and James) ... understand a smaller modern board will be more challenging to balance ...
    (rec.windsurfing)