Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
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




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



