Re: Surrogate factoring, more theory

From: Nora Baron (norabaron_at_hotmail.com)
Date: 02/08/05 

Date: 7 Feb 2005 17:50:36 -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)
>
> 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.
>

  I don't see why you say "x is defined by the factorization of
T and j^2." It looks like x is a function of T and j^2, but
it appears not to be dependent on how they are factored.

  I can see that z is a factor of j^2, and clearly also x is a
factor of M^2. However, in the equation just above for x,

  x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)

it is clear that x is not dependent on a factorization of
T. Note that T itself, not factors of T, appears in only
one place in the expression for x. The same is true for your
expression for z. Factoring T seems to have no effect at all
on x or z, because it is not separated *factors* of T which
appear in those expressions, it is only T itself.

> 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!
>

  No, I don't see that x depends at all on a factorization
of T. What you have above does not show that.

> 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.
>

  Maybe because in the expression for x, you do not separate out the
factors of T. The only thing that appears is T itself, not its
factors. Factoring this "surrogate" does not work its way through
your formulas since you do not examine those factors separately.

> 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?
>

  In the sqrt expression you just gave, neither the factors of T
nor the factors of j appear. Factoring them has no effect. You
want the expression inside to be a perfect square, i.e., you want
to choose x so that the stuff inside the square root is a perfect
square. But choosing such x depends only on the values of j and
T themselves, not on how they are factored. So what good does
"surrogate factoring" do? Nowhere above do you show any factor-
ization of T. Your original approach to this seemed to make more
sense.

  Nora B.

>
> James Harris

Relevant Pages

  • Proper evaluation of surrogate factoring
    ... Surrogate factoring is just kind of a wild idea that means you have to ... I am being very serious here, modern mathematicians lie a lot. ...
    (sci.crypt)
  • Re: SF: Areas of confusion, infinity
    ... > notably the set of rationals. ... choosing any integer is the same as the probability of any other ... That's what make the factoring problem interesting, i.e., not ... > is naive with the surrogate factoring theorem. ...
    (sci.crypt)
  • Re: What surrogate factoring theory now says
    ... Surrogate factoring theory says that you can turn factoring a hard ... once the engineering is figured out that is achievable. ... Mainly I just added one more congruence to the difference of squares. ...
    (sci.crypt)
  • Re: What surrogate factoring theory now says
    ... Surrogate factoring theory says that you can turn factoring a hard ... once the engineering is figured out that is achievable. ... Mainly I just added one more congruence to the difference of squares. ...
    (sci.crypt)
  • Surrogate factoring, theory versus implementation
    ... the surrogate factoring method is itself being called to ... Now the discussions can go on indefinitely as posters who reply to me ... It's in its failures that my primary interest lies. ...
    (sci.crypt)
Quantcast