Surrogate factoring, objective look

jstevh_at_msn.com
Date: 02/09/05 

Date: 9 Feb 2005 04:09:49 -0800

I have found a factorization method which I claim is new and important.
 Here is an attempt at being objective about my own finding, by
explaining how it works, and comparing it with congruence of squares.

Congruence of square relies on a simple idea to factor numbers using
quadratics.

Say you have f_1 f_2 = M. Consider the quadratic

x^2 + cx - M = 0, where you trivially have x(x + c) = M,

so if all all are integer x must be a factor of M, but if it's 1 or M,
it's a trivial factor.

Solving that quadratic is easy enough using the quadratic formula, and
you get

x = (-c +/- sqrt(c^2 + 4M))/2

and if that square root is an integer, then you have an integer x.

Most modern factoring techniques, especially the most powerful ones,
like the Number Field Sieve derive from that basic idea.

To get a good overview and independent verification, see the Wikipedia:

http://en.wikipedia.org/wiki/Congruence_of_squares

What I did was concentrate on two quadratics instead of one, with a bit
more complexity as I have

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 again
the
target to be factored, and you find that you can use T, where

T = M^2 - j^2

and solving for y with one equation and substituting it into the other
allows you to solve for x and z to 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)

where there are two key difference from congruence of square shown
before, as x can be a fraction, but importantly while a factor M, is
dependent on the factorization of Tj^2 to be rational, and z is
dependent on the factorization of TM^2, as you can see in those
equations by looking at the square roots.

That is how you can see that what I call surrogate factoring is a new
method for factoring.

That is news, in and of itself.

Now from a new way to look at factoring, to finding working programs
that factor well can take some time. But still, it's new knowledge in
an important area. Read carefully posts on these newsgroups to see how
the information is treated.

It is math remember. Truth can be determined in mathematics.

James Harris

Relevant Pages

  • Re: JSH: SF: Simpler factoring idea, but does it work?
    ... Here the square roots mean that expression can't just factor S, ... Including a rigorous proof that it was in fact 100% useless -- although some ... and you need S, and can use any square you like, so it's easiest just ... But does it work beyond toy examples like factoring 15? ...
    (sci.math)
  • Integer factorization, basics
    ... The factoring problem concerns itself with finding non-trivial values ... square that adds to 4M to get a square, then you have a value of 'b' ... and you may choose to do so now, for whatever reasons are motivating ...
    (sci.math)
  • Re: Integer factorization, basics
    ... > The factoring problem concerns itself with finding non-trivial values ... > So the congruence of squares method works by having the square root ... > Being large primes, they are rare. ...
    (sci.math)
  • Re: Surrogate factoring, more theory
    ... > At the heart of surrogate factoring there are two quadratics: ... > analysis of the quadratics, and one of the simplest is just to ... want the expression inside to be a perfect square, i.e., you want ...
    (sci.math)
  • Re: Surrogate factoring, more theory
    ... > At the heart of surrogate factoring there are two quadratics: ... > analysis of the quadratics, and one of the simplest is just to ... want the expression inside to be a perfect square, i.e., you want ...
    (sci.crypt)