Simplifying discussion on surrogate factoring

jstevh_at_msn.com
Date: 03/23/05 

Date: 23 Mar 2005 04:14:19 -0800

Now I can at least give a more general exposition on surrogate
factoring by focusing on a single quadratic, in the *hope* that maybe
something can be resolved, though now there are posters--surprise,
surprise--who are clearly working to simply disrupt discussion with
their posts.

Focusing on the single quadratics

yz^2 - Az + j^2 = 0

where j is some non-zero integer that you choose, it's clear that if
you have some integer M in mind, with j coprime to M, there is no
reason to think that quadratic or its solutions are at all related to
the factors of M.

But I can introduce a relationship in a very easy way by using

T = M^2 - j^2,

and adding T to both sides which gives

yz^2 - Az + M^2 = T

and from there I can solve to get

Az = f_1 b_2 + f_2 b_1 - 2M^2

where

f_1 f_2 = T and b_1 b_2 = M^2

and I've introduced a relationship between factors of M, and T, and a
root of the previous quadratic times A, from that quadratic.

So what does Az have to do with roots of M?

Nothing.

However, f_1, f_2, b_1 and b_2 can be *rationals* so that equation is
actually talking about finding rationals such that you get the
relationship.

That's why I've talked about this method relying on the entire set of
rationals, as it does.

Basically if any rational factors of T and M exist, such that

Az = f_1 b_2 + f_2 b_1 - 2M^2

then you can get those solutions out, as it's easy enough to solve for
one of them, like you have

b_2 f_1 = (Az + 2M^2 +/- sqrt((Az + 2M^2)^2 - 4M^2T))/2

found simply enough by using the substitution

b_1 = M^2/b_2

and here you get a difference of squares, as somehow Az has been
related to M, where T clearly is important.

Now imagine you already know M's factors, and with them pick some
rationals to get Az from

Az = f_1 b_2 + f_2 b_1 - 2M^2

then you know that will fit into the solution for b_2 f_1, and it
raises the question of, well what if you don't know those factors, can
you just check Az values to try and get them?

That's where surrogate factoring comes into it, as that's the idea of
it, to get those factors of M, from using other factorizations.

It turns out you can delve more deeply into the question of those
rational factors, as you can simply consider

b_1 = (g_1 d_2)/d_1

and

b_2 = (g_2 d_1)/d_2

where g_1, g_2, d_1, and d_2 are integers, as notice then

b_1 b_2 = ((g_1 d_2)/d_1)((g_2 d_1)/d_2) = g_1 g_2

so I can have g_1 and g_2 be integers, and consider ALL possible
rational factors of M.

Making the substitutions for b_1 and b_2 and simplifying a bit gives

 Az d_1 d_2 = f_1 g_1 d_2^2 + f_2 g_2 d_1^2 - 2M^2 d_1 d_2

so considering d_1 and d_2 you get a conic section.

That is, assuming you have all the other values and wish to know if
there exists integers d_1 and d_2, the curve of the solution for all
possible complex values for d_1 and d_2 is a conic.

It turns out that whether it's elliptic or hyperbolic depends on the
sign of T.

If T is positive, then it's elliptic.

If T is negative then it's hyperbolic.

The gist of it then is that somehow I've related this quadratic with an
arbitrary integer

yz^2 - Az + j^2 = 0

with conics, in order to relate to the factorization of M.

If you can solve either of the conics, then you can factor M.

James Harris

Relevant Pages

  • JSH: Factoring
    ... and there is this remarkable relationship that shows a connection ... but that STILL leaves the huge set of rationals for b_1 and b_2 to ... And if you know anything about factoring, you know that I have Az setup ... I think that these quadratics may be beyond most of you. ...
    (sci.math)
  • Simplifying discussion on surrogate factoring
    ... factoring by focusing on a single quadratic, ... Focusing on the single quadratics ... actually talking about finding rationals such that you get the ... If you can solve either of the conics, ...
    (sci.math)
  • Surrogate factoring ideas to ponder
    ... Part of the reason I find myself still focusing on a sign variation on ... my earlier quadratics is that I can easily get to a surprising ... quadratic, but importantly, b_1 and b_2 can be rationals. ... selection. ...
    (sci.math)
  • Surrogate factoring ideas to ponder
    ... Part of the reason I find myself still focusing on a sign variation on ... my earlier quadratics is that I can easily get to a surprising ... quadratic, but importantly, b_1 and b_2 can be rationals. ... selection. ...
    (sci.crypt)
  • JSH: Factoring, number theory
    ... So now with the easy proof, there's not an issue of whether or not ... That's not terribly surprising in retrospect because it's a finite set. ... factoring problem would not have been considered such a difficult one. ... It only took *two* quadratics while most factoring is based on ideas ...
    (sci.math)