Re: Surrogate factoring, more theory

jstevh_at_msn.com
Date: 02/08/05 

Date: 8 Feb 2005 04:13:42 -0800

jstevh@msn.com wrote:
> At the heart of surrogate factoring there are two quadratics:
>
> yx^2 + Ax - M^2 = 0
>
> and
>
> yz^2 + Az - j^2 = 0
>
> where A, j, and M are integers greater than 0 chosen, where M is the
> target to be factored, and that is done through factoring the
surrogate
> T, which is
>
> T = M^2 - j^2
>
> and one intriguing assertion I've made is that the value of A, other
> than being an integer greater than 0, doesn't matter.
>
> That assertion can be seen to be true multiple ways through basic
> analysis of the quadratics, and one of the simplest is just to
> substitute out y, and solve for x and also to solve for z, as then
you
> get
>
> x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)
>
> and
>
> z = x(-Ax +/- sqrt((Ax - 2j^2)^2 - 4Tj^2))/(2M^2 - 2Ax)

OOPS!

Should be

z = x(-Ax +/- sqrt((Ax + 2j^2)^2 - 4Tj^2))/(2M^2 - 2Ax)

> and you can see a lot from those formulas, like how z is defined by
the
> factorization of T and M^2, while x is defined by the factorization
of
> T and j^2, which kind of gives you the idea of how surrogate
> factorization is supposed to work.
>
> Also note that quite simply assertions that the method is just
> congruence of squares can be seen to be false, as, in fact, x is
> dependent on the factorization of T and j^2 despite being a factor M,
> since
>
> x(yx + A) = M^2
>
> just using yx^2 + Ax - M^2 = 0, as that's kind of the neat part of
> surrogate factoring, as somehow I've managed to make things
> topsy-turvy, which is interesting from a "pure math" stand point, but
> the practical wish is to factor!
>
> Oh, don't bother trying to loop through one to force a factorization
of
> the other as I tried that, and it didn't work. I don't know why.
>
> But, back to A, as notice that it has no impact on the solutions, as
if
> x is a factor of M, for one A, it is for all of them, though, I
guess,
> if you had A have a factor of M it could cancel out x, but then,
you'd
> have the factor of M, and you choose A, so it is in fact a
non-factor.
>
> However, if A is unimportant, then how do solutions for y get chosen?
>
> And why exactly can't I just pull out a factorization of M, from
> letting A=1, and just getting integer x's from the solution for z,
and
> then, end up with x's that are factors of M.
>
> But I tried that, and with my programs it didn't work.
>
> But if A is unimportant, what decides? How do you solve
>
> sqrt((Ax - 2j^2)^2 - 4Tj^2))
>
> to get an x that gives a non-trivial factor of M?
>
> Why doesn't it work? I think I have theory worked out, but I've
> programmed it and it doesn't work. But why not?
>
>
> James Harris

Relevant Pages

  • Surrogate factoring, top to bottom
    ... The best way to understand surrogate factoring may be to to start with ... So, trivially, every factorization of any given target composite T is ... and the mathematics does not say ...
    (sci.crypt)
  • Surrogate factoring, more theory
    ... At the heart of surrogate factoring there are two quadratics: ... That assertion can be seen to be true multiple ways through basic ...
    (sci.math)
  • Re: Surrogate factoring, more theory
    ... > At the heart of surrogate factoring there are two quadratics: ... > and one intriguing assertion I've made is that the value of A, ... > analysis of the quadratics, and one of the simplest is just to ... > factorization of T and M^2, while x is defined by the factorization ...
    (sci.math)
  • Surrogate factoring, more theory
    ... At the heart of surrogate factoring there are two quadratics: ... That assertion can be seen to be true multiple ways through basic ...
    (sci.crypt)
  • Re: Surrogate factoring approach, analysis
    ... >> It turns out that the analysis behind my surrogate factoring ... Each is the product of two primes whose length is up to ... Each factorization is taken a few minutes now... ... the target, which I call M. ...
    (sci.math)
Loading