Re: Reality check, surrogate factoring

From: Rick Decker (rdecker_at_hamilton.edu)
Date: 01/27/05 

Date: Wed, 26 Jan 2005 21:22:48 -0500

Tim Smith wrote:

> In article <1106707007.031093.186480@z14g2000cwz.googlegroups.com>,
> jstevh@msn.com wrote:
>
>>But, you're factoring T, where T = M^2 - j^2, where M is your target, and
>>j is picked. Like typically j is odd, as M is odd (though you may need to
>>make it even, more later), and you can also pick j such that T is
>>divisible by 3, or such that it is divisible by any number you wish it to
>>be.
>>
>>You also get a partial factorization of T at the outset as
>>
>>T = (M-j)(M+j)
>>
>>so what I'm saying is that some people somewhere work really hard to pick
>>p_1 and p_2 so that p_1 p_2 is hard to factor by known methods, and
>>surrogate factoring allows you to blow all of that out of the water by
>>shifting to another number, easy to factor.
>
>
> You should give examples, using small integers. E.g., pick a couple of 2
> digit primes, multiply them, and show how your methods would be used to
> factor that product.
>
He probably won't, so here's my interpretation, using 1-digit primes.

Let M, the number to be factored, equal 15.

James picks an arbitrary j (which we'll say is 2 for this example)
and lets T = M^2 - j^2. In this case,

    T = 15^2 - 2^2 = (15 + 2)(15 - 2) = 17 * 13 = 221

Now factor T and -j^2. A good starting point is to use the factorization
above for T, namely f_1 = 17, f_2 = 13. Since j is small, we can factor
it easily, say as b_1 * b_2, where b_1 = -4, b_2 = 1.

For some rationals, a_1 and a_2, take the two terms

    a_1 x + b_1 = f_1
    a_2 x + b_2 = f_2

and multiply them, yielding

    a_1 a_2 x^2 + (a_1 b_2 + a_2 b_1)x + b_1 b_2 = f_1 f_2

In our case, that gives us [EQ 1]

    a_1 a_2 x^2 + (a_1 (1) + a_2 (-4))x + (-4)(1) = 17 * 13

Now, using the facts that b_1 b_2 = -(j^2), f_1 f_2 = T = M^2 - j^2
we see that

    a_1 a_2 x^2 + (a_1 b_2 + a_2 b_1)x - j^2 = M^2 - j^2

so

    a_1 a_2 x^2 + (a_1 b_2 + a_2 b_1)x = M^2

so

    x(a_1 a_2 x + a_1 b_2 + a_2 b_1) = M^2

so x is a factor of M^2, which is what we wanted.

Now, for this to have any use, we'd at least want x to be rational.
So x must be a rational solution of the equation

    a_1 a_2 x^2 + (a_1 b_2 + a_2 b_1)x - M^2 = 0

Well, it's easy enough to find x:

    x = (-(a_1 b_2 + a_2 b_1)
         +/- sqrt((a_1 b_2 + a_2 b_1)^2 + 4M^2 a_1 a_2) / (2 a_1 a_2)

and for x to be rational, we need the discriminant

    (a_1 b_2 + a_2 b_1)^2 + 4M^2 a_1 a_2

to be a rational square.

It turns out that we can (almost) always find a_1 and a_2 that will
guarantee this. The details aren't germaine to this discussion, but
you can verify that a_1 = 45/2, a_2 = 1 will work quite nicely.
Putting these values into [EQ 1] gives us

    ((45/2)x - 4)(x + 1) = 17 * 13

so we obtain the quadratic

    (45/2)x^2 + (37/2)x - 4 = 17 * 13

or

    (45/2)x^2 + (37/2)x - 225 = 0

Now, solving for x we find that

    x = -18/5, 25/9

Of course, since we're in the realm of the rationals, "factor" is
almost completely meaningless, but James does something that's
fairly common in factoring, namely, he looks at the numerators
of the x values. While I don't think he says it in his exposition,
a quick way to do this is to compute gcd(numerator(x), M). If
we do this in our example, we see that

    gcd(-18, 15) = 3 and gcd(25, 15) = 5

so whadda you know, in this case we were lucky enough to find
both of the factors of 15. It's not a big step to then compute

    15 = 5 * 3

Wow.

That, in a nutshell, is my take on Harris factorization.
I should note that this is not exactly what James is
doing in his paper--I've concentrated on the parts that
aren't obviously in error and tried to deobfuscate as
much as I could.

We've left off some relevant questions:

1. In my example, it appears that j = 2 was a lucky choice.
    How far do we have to search among the j's to get an
    x that has a *nontrivial* (ie., not 1 or M) factor
    in common with M? If M were a 200-digit composite, for
    example, would we have to look through 10^100 candidates
    for j?

2. In my example, all we had to do was use the "obvious"
    factors 17 and 13 of T. If M was a 200-digit number
    and none of the choices for j gave us a useful x,
    would we have to (somehow) factor T further to get
    some f_1 and f_2 that would yield a useful result,
    given that each of the obvious factors is about 200
    digits long?

3. Although I didn't explain it, finding the a's is
    easy. Finding *all* possible a's for which x is
    rational requires another factorization. Do we
    ever have to do this, and if so, can it be done
    quickly? The number we'd have to factor is
    approximately as large as M^2.

Hope this helps. I apologize for the length.

Regards,

Rick

Relevant Pages

  • 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: I was right, surrogate factoring proof
    ... > Tim Peters wrote: ... >>James is certainly right that for any rationals x and z, ... be factors of -4Tj^2 that will lead to a factorization of M-- ... Regards, ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... > Tim Peters wrote: ... >>James is certainly right that for any rationals x and z, ... be factors of -4Tj^2 that will lead to a factorization of M-- ... Regards, ...
    (sci.crypt)
  • 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.math)
Loading