Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: SF: Finally, surrogate factoring
Replies: 86   Last Post: Jun 10, 2006 11:51 PM

 Messages: [ Previous | Next ]
 Rick Decker Posts: 1,356 Registered: 12/6/04
Re: SF: Finally, surrogate factoring
Posted: Jun 5, 2006 3:32 PM

jstevh@msn.com wrote:
> Solving the Factoring Problem
>
>
> Consider a relation between two integer factorizations:
>
> f_1 f_2 = k + g_1 g_2
>
> and a solution with four unknowns w, x, y and z, as they are determined
> by four linear equations:
>
> L_1(w,x,y,z) = f_1
> L_2(w,x,y,z) = f_2
> L_3(w,x,y,z) = g_1
> L_4(w,x,y,z) = g_2
>
> What I have found is that remarkably you can use only two linear
> equations and k itself to find
> g_1 and g_2, through a process I call surrogate factorization.

Indeed you can (subject to the corrections below), but as a
factoring algorithm it sucks big time. Remember, to be of
any worth whatsoever, a factoring algorithm must not only work,
but it must be efficient. Yours is worse than trial division.
>
> More specifically I use the system of equations
>
>
> (w + x - 2z)(w + 3x + 2y + 2z) = k + (w + x + y + z)(3w + x - y - 3z)
>
> where
>
>
> k = 2x^2 + 2xy + y^2 - 2w^2 - z^2 - 2xz
>
> as then I can use
>
>
> w + x - 2z = f_1
>
> w + 3x + 2y + 2z = f_2
>
>
> to find
>
> x = (f_2 - f_1 - 2y - 4z)/2, w = (3f_1 - f_2 + 2y + 8z)/2
>
> and with
>
> f_1 f_2 = T+k
>
> where T = (w + x + y + z)(3w + x - y - 3z)
>
> I have that
>
> 9(2y + 10z + 5f_1 - f_2)^2 = (18z + 6f_1 - 2f_2)^2 - 18T - 54k +
> 45f_2^2 - 99f_1^2
>
> (But it's a tedious calculation where it's easy to make a mistake.
> Note that k, x and w above have been carefully verified and I tried my
> best with the calc, but may have gotten it wrong.

You did get it wrong. However, the identity

(2y + 10z + 5f_1 - f_2)^2 = (4z +3f_1 - f_2)^2 + 4T

is correct (not that this is of any use).

Regards,

Rick

Date Subject Author
6/4/06 JAMES HARRIS
6/5/06 Doug Schwarz
6/5/06 Tim Peters
6/5/06 Doug Schwarz
6/5/06 Christopher J. Henrich
6/5/06 Gib Bogle
6/5/06 Proginoskes
6/5/06 William L. Bahn
6/5/06 JAMES HARRIS
6/5/06 Abstract Dissonance
6/5/06 Abstract Dissonance
6/5/06 Salami Man
6/5/06 William L. Bahn
6/6/06 Brian Quincy Hutchings
6/5/06 guenther.vonKnakspott@gmx.de
6/6/06 Matthijs Hebly
6/6/06 Salami Man
6/5/06 Abstract Dissonance
6/5/06 Gordon Burditt
6/5/06 Sebastian Gottschalk
6/5/06 dkguru
6/5/06 Ed Weir \(ComCast\)
6/5/06 Abstract Dissonance
6/5/06 Andrew Swallow
6/5/06 gjedwards@gmail.com
6/5/06 Salami Man
6/5/06 Gib Bogle
6/6/06 TC
6/6/06 Salami Man
6/5/06 Sebastian Gottschalk
6/5/06 JAMES HARRIS
6/5/06 marc.t.davies@gmail.com
6/5/06 gjedwards@gmail.com
6/5/06 LarryLard
6/5/06 William L. Bahn
6/5/06 Richard Henry
6/5/06 Salami Man
6/5/06 Bob Marlow
6/5/06 Bob Marlow
6/5/06 none
6/5/06 rossum
6/5/06 Rick Decker
6/5/06 JAMES HARRIS
6/5/06 jshsucks@yahoo.com
6/5/06 Salami Man
6/5/06 Tim Peters
6/5/06 JAMES HARRIS
6/5/06 Tim Peters
6/6/06 Rick Decker
6/6/06 Rick Decker
6/6/06 Tim Peters
6/6/06 Rick Decker
6/7/06 David C. Ullrich
6/7/06 Rick Decker
6/7/06 Jesse F. Hughes
6/7/06 Rick Decker
6/8/06 David C. Ullrich
6/7/06 Bertie Reed
6/6/06 JAMES HARRIS
6/6/06 JAMES HARRIS
6/7/06 Rick Decker
6/7/06 Tim Peters
6/7/06 Rick Decker
6/8/06 JAMES HARRIS
6/8/06 Jose Carlos Santos
6/8/06 Rick Decker
6/8/06 LarryLard
6/8/06 David Bernier
6/8/06 Rick Decker
6/9/06 Tim Peters
6/9/06 david250@gmail.com
6/9/06 marcus_b
6/8/06 Richard Henry
6/8/06 jshsucks@yahoo.com
6/8/06 Paul Sperry
6/8/06 LarryLard
6/8/06 Denis Feldmann
6/8/06 David Bernier
6/8/06 David C. Ullrich
6/8/06 David Moran
6/8/06 David Bernier
6/8/06 Tim Peters
6/8/06 Proginoskes
6/10/06 Tim Peters
6/10/06 Tim Peters
6/6/06 gjedwards@gmail.com
6/6/06 Proginoskes