Factoring problem solution

jstevh_at_msn.com
Date: 02/10/05 

Date: 10 Feb 2005 04:17:21 -0800

I've been working to figure out the particulars of my approach to
surrogate factoring focusing on getting solutions for y, and then
using those to get solutions for x, as it's a little complicated.

It turns out there's an easier way, where you focus on x at the start,
and actually solve out y, and at a key point you do an inversion to
get the full solution set, solving the problem.

Notice the mathematics is very easy. The factoring problem had never
been proven to be difficult, but had been supposed to be difficult
because no one knew of an easy answer!

Well, here it is.

Take the 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 you find that you can use T, where

T = M^2 - j^2

and substituting out y to solve for x and z gives

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)

where you have the problem that x may be a fraction, and its
denominator is what's important to determine.

So, invert it. Let x = 1/Aw, then

z = 1(-1/w +/- sqrt((1/w - 2j^2)^2 + 4Tj^2))/(2wM^2 - 2)

and focusing on the square root I have

sqrt((1 - 2wj^2)^2 + 4Tw^2 j^2))/w^2

and focusing on the square root again, multiplying it out, gives

sqrt(1 - 4 j^2 w + 4j^4 w^2 + 4Tj^2 w^2)

and collecting with respect to w, gives

sqrt(4(j^4 + Tj^2)w^2 - 4A^2 j^2 w + 1)

which is

sqrt(4j^2 (j^2 + T)w^2 - 4 j^2 w + 1)

and since M^2 = j^2 + T, that is

sqrt(4j^2 M^2 w^2 - 4j^2 w + 1)

and completing the square inside, gives

sqrt(4j^2 M^2 w^2 - 4j^2 w + j^2/M^2 + 1 - j^2 /M^2)

which is

sqrt((2j M w - j/M)^2 + (M^2 - j^2)/M^2)

which is

sqrt(j(2M^2 w - 1)^2 + T)/M^2

and focusing on the square root again, you have

sqrt(j(2M^2 w - 1)^2 + T)

showing that the factorization is dependent on T.

The inversion is what's necessary to finish out.

Since x = 1/Aw, if x is a fraction like

x = x_num/x_denum, where x_num and x_denum are integers, then

w = x_denum/A x_num

so you can easily recover x from the solution to w, and you can let A
have different values but it's easier to just let A=1, as you don't
gain anything using other values.

That means the solution is almost trivially easy, and not hard to
implement.

The belief that factoring was a hard problem had nothing to do with
mathematical reality, but simply human wants and needs.

James Harris

Relevant Pages

  • Re: implementing the quadratic sieve
    ... >are familiar with the quadratic sieve, ... >Quadratic Sieve factoring algorithm: ... Call the square root of the product of the prime factors y. ... The ultimate truth is that there is no Ultimate Truth ...
    (comp.programming)
  • Prime numbers and the RSA algorithm
    ... depends upon the impracticality of factoring N back into p and q. ... If it is easy to check p for primeness, ... by factorization or by dividing ... it by every number between 2 and the square root of N. ...
    (sci.math)
  • Re: The hardest Euler problem
    ... cac writes Re: The hardest Euler problem ... What else to expect with a built-in number-of-divisors function? ... factoring that I don't. ... square root of u1, because each successful division delivers you two ...
    (comp.lang.forth)
  • Factoring problem solution
    ... The factoring problem had never ... where you have the problem that x may be a fraction, ... and focusing on the square root again, multiplying it out, gives ... The belief that factoring was a hard problem had nothing to do with ...
    (sci.crypt)
  • Re: Surrogate factoring, a fascinating idea
    ... > If mathematicians just ignore the result, however, and someone out ... > factoring is a hard problem. ... Bartosz Zoltak ...
    (sci.crypt)
Loading