Re: Factoring problem, my assertion revisited

From: Rick Decker (rdecker_at_hamilton.edu)
Date: 02/09/05 

Date: Tue, 08 Feb 2005 22:47:31 -0500

Décio Luiz Gazzoni Filho wrote:

> Rick Decker wrote:
>
>><snip>
>>
>>I'm pretty sure I've posted a sample using James' method to factor 15.
>>I have another one factoring 391 if anyone's interested.
>
>
> I am. Did you do that by hand, or have you written a program to do it?

I did it by hand. I'm not willing to take the time to program it
until I have at least some reason for believing that it would be
worth the effort.
>
> An example with a very large composite would be appreciated, to evaluate the
> difficulties of finding all variable required for a successful
> factorization using James' method.
>
Okay, Décio (and Tim), here it is. Since a lot of the method takes place
in the rationals, I've simplified things a bit by rescaling some of the
numbers. It does, however, capture what I think is James' argument. If
you compare this with what James has written, notice that I've set A
to be 1/2 at the start. In fact, it doesn't matter what value you pick.

Consider the two equations

    yx^2 + x/2 = (M^2)/4 [1]
    yz^2 + z/2 = (j^2)/4 [2]

where M is the number to be factored and j is some integer, 1 <= j < M.
We are interested in x, since (assuming M is odd), num(x), the numerator
of the rational x, has at least a chance of dividing M, especially
if we concentrate on gcd(num(x), M).

Then, from [1]

    y = (1/x^2)((M^2)/4 - x/2)

and if we substitute this into [2] we have

    (1/x^2)((M^2)/4 - x/2)z^2 + z/2 - (j^2)/4 = 0

or

    ((M^2)/4 - x/2)z^2 + (x^2)z / 2 - (j^2 x^2) / 4 = 0

Look at this as as a quadratic in z and consider the discriminant

    (x^4)/4 + 4((j^2 x^2)/4)((M^2)/4 - x/2)
     = ((x^2)/4)(x^2 + M^2 j^2 - 2x j^2)
     = ((x^2)/4)(x^2 - 2 x j^2 + j^4 - j^4 + M^2 j^2)
     = ((x^2)/4)((x - j^2)^2 - j^4 + M^2 j^2)
     = ((x^2)/4)((x - j^2)^2 + j^2 (M^2 - j^2))
     = ((x^2)/4)((x - j^2)^2 + j^2 T)

letting T = M^2 - j^2.

Now we want this to be a rational square (to make z rational), so
we must have

    (x - j^2)^2 + j^2 T = r^2

For some rational r. Thus we have

    (x - j^2)^2 - r^2 = -j^2 T = g_1 g_2

for some integers g_1 and g_2. Then we have a possible decomposition

    (x - j^2) + r = g_1
    (x - j^2) - r = g_2

from which we can conclude

    x = (g_1 + g_2 + 2j^2) / 2

Thus, if we can find the factors g_1 and g_2 of -j^2 T, we might have a
chance that num(x) will have a factor in common with M.

[There are some things I've left out here, like the fact that if p is
a prime dividing M, then g_1 + g_2 + 2j^2 = 0 mod p iff g_1 = g_2 = -j^2
mod p^2.]

Let's try two examples, using M = 391 = (17)(23), not, I admit, a
very "large" composite.

1. j = 3: In this case T = (M + j)(M - j) = (394)(388), so -j^2 T =
    -(2^3)(3^2)(97)(197) for a total of 96 factors (counting negatives)
    This gives us the (usual) default factors (-3)(394) and (3)(388),
    which when used for g_1 and g_2, give us an x with gcd(num(x), M)=M,
    which I've taken to calling "useless" factors.

    However, if we factor -j^2 T as (g_1)(g_2) = (8)(-9*97*197) =
    (8)(-171981), we have g_1 + g_2 + 2j^2 = 8 - 171981 + 18 =
    -171955 = (17^2)(595), so this factorization gives us a
    factor, 17, of M.

    If we keep trying, we might also stumble on (-9)(152872),
    which yields the other nontrivial factor, 23, of 391.

2. j = 2: this is an interesting choice, since we have
    -j^2 T = -(2^2)(3)(131)(389) for a total of just 48 factors.
    In this case, none of the factor pairs (g_1)(g_2) give us
    an x for which gcd(g_1 + g_2 + 2j^2, M) is anything other
    than 1 or M.

    Part of the problem here is that in order to get a useful
    factor of M, we need -g_1 and -g_2 both to be quadratic
    residues mod p^2 for some p dividing M, which is what I meant
    in another post when I said we don't want to have too few
    possible factors of j^2 T, since we might not have any that
    satisfy the needed condition.

So there you have it. The crux of this method seems to me to
contain two related questions: how can you pick j so that

a. There will be at least some useful factors, unlike my
    "bad" choice j = 2 above?

b. j^2 T will be easy to factor, but not too easy, in the sense
    that the sample space will be large enough to yield "good"
    factors, but not so large that you have to try more than
    some power of log M samples? James claims that all one
    needs to do is factor T--that's unproven, and even if it
    were true it doesn't seem to help very much.

Hope this helps; I apologize for the length.

Regards,

Rick

Relevant Pages

  • Re: surrogate factoring
    ... quality "SF time" than anyone other than James ... ... "surrogate factoring" doesn't really mean anything specific. ... since the set of all non-zero rationals constituted the search space ... pushing formulas around, and it may be a bona fide compulsion for him. ...
    (sci.math)
  • Re: surrogate factoring
    ... quality "SF time" than anyone other than James ... ... "surrogate factoring" doesn't really mean anything specific. ... since the set of all non-zero rationals constituted the search space ...
    (sci.math)
  • Re: JSH: What will you do?
    ... I *still* don't see how these number yield the integer factors of 15. ... SFT is mind-numbingly ... ... First, James doesn't have an algorithm this time, just "a theorem". ...
    (sci.math)
  • Re: JSH: What will you do?
    ... > number yield the integer factors of 15. ... SFT is mind-numbingly ... ... First, James doesn't have an algorithm this time, just "a theorem". ... infinite number of rationals f_1 such that ...
    (sci.math)
  • Re: Factoring problem, my assertion revisited
    ... Décio Luiz Gazzoni Filho wrote: ... >>I'm pretty sure I've posted a sample using James' method to factor 15. ... >>I have another one factoring 391 if anyone's interested. ... in the rationals, I've simplified things a bit by rescaling some of the ...
    (sci.math)
Quantcast