SF: Simpler derivation

jstevh_at_msn.com
Date: 03/05/05 

Date: 5 Mar 2005 10:04:02 -0800

Well now that I figured it out one way NOW wouldn't you know, it's
obvious the easy way.

With

yx^2 + Ax - M^2 = 0

and

yz^2 + Az - j^2 = 0

and T = M^2 - j^2

let x = zr, where r is a prime factor of M, then

yr^2 z^2 + Arz - M^2 = 0

with

yz^2 + Az - j^2 = 0

so multiplying the second by r^2, I have

yr^2 z^2 + Arz - M^2 = 0

with

yr^2 z^2 + r^2 Az - r^2 j^2 = 0

and subtracting the first from the second gives

(r^2 - r)Az = r^2 j^2 - M^2

and dividing gives

Az = (j^2(r + 1) - T/(r-1))

as I gave before.

Now the importance of Az comes from those other equations where it's
shown to be related to the factorization of M so that it must have a
single prime factor of M for some integer Az.

The weird thing is that it's so simple but it must work.

Notice here you can also see why j and M need to be odd, as if j is
even, while M is odd, and r is then odd as it's a prime factor of M,
then

(r^2 - r)Az = r^2 j^2 - M^2

means you have an even right side versus and odd left.

That makes a difference not worth fiddling with, as the power of 2 on
the left is dependent on r-1, which means it depends on the prime
factor you're trying to find!

That may still be a problem though even with odd j and odd M, as I'm
not sure that T will necessarily catch all of the powers of 2, but if
it does not, and you do a single pass and don't get a factorization,
then you know that is the only reason that it can happen, and it's easy
to shift j to put more factors of 2 in T, or even to multiply M by a
cracking prime.

Notice also that *both* prime factors of M would have to have
significant powers of 2. Like if you have 17 as a factor, then you'll
need to handle 2^4, only if the other prime minus one has 2^4 as a
factor.

And even if they both do, you can multiply by some prime like 7, to
crack, forcing the factorization.

I can't believe it's this easy. I'm still wondering, but the math is
just so simple.

The factoring problem then is just some basic algebra that kids can
learn.

All that fuss over something so simple.

James Harris

Relevant Pages

  • Re: Polynomial time factoring algorithm?
    ... But what if S is your target composite to be factored? ... from working, like if S is odd then T must be odd, and f_1 and f_2 ... non-trivial factorization of your target composite S. ... factoring congruences. ...
    (sci.crypt)
  • SF: Simpler derivation
    ... so multiplying the second by r^2, ... Notice here you can also see why j and M need to be odd, ... it does not, and you do a single pass and don't get a factorization, ... significant powers of 2. ...
    (sci.crypt)
  • Re: Reality check, surrogate factoring
    ... Like typically j is odd, as M is odd (though you may need to ... James picks an arbitrary j ... A good starting point is to use the factorization ... Of course, since we're in the realm of the rationals, "factor" is ...
    (sci.crypt)
  • Re: Reality check, surrogate factoring
    ... Like typically j is odd, as M is odd (though you may need to ... James picks an arbitrary j ... A good starting point is to use the factorization ... Of course, since we're in the realm of the rationals, "factor" is ...
    (sci.math)
  • Re: Little conjecture
    ... any such expression can be written as an odd number ... that Chas fewer than 2k powers of 2, so that when all powers ... Certainly looking at the original product, the numerator ... Obviously from the original form, ...
    (sci.math)