Re: JSH: SF: Finally, surrogate factoring

Rick Decker wrote:
Rick Decker wrote:



Tim Peters wrote:

[added "JSH:" to subject, spared sci.crypt and alt.math]

[jstevh@xxxxxxx]

...
And it has been posted in this thread that I DID get it wrong.

If you do it right, it shows a dependency on the factorization of T,
which is no good.

But what if you go the other way, isolating y on the right side,
instead of z?

So instead, you would complete the square twice isolating z on the left
and with the second you would get y inside the square on the right.

The reason for wondering is that if you solve for z using the four
linear equations, yup, it does solve in such a way that you can have a
difference of factors of T, but y does not.

Long-shot.

... and a miss.



I got

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

then, but didn't care enough to double-check it.

That's what I got, too. Mathematica agrees.

(Responding to my own post...)

So completing the square w.r.t y first yields

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

Completing the square w.r.t. z first yields

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


The only problem I have with that is that you have too many solutions
for y.

There is one explicit solution for y given by solving the 4 linear
equations.

That solution is

y = (7g_1 - 3g_2 + 5f_1 - 3f_2)/4

which what you give covers, but you could have gotten that by working
backwards FROM the explicit solution, and there is one problem.

If T has only two prime factors p_1 and p_2, there are 8 possible
values for y for a given f_1 and f_2, which represent g_1 = T, p_1,
p_2, or 1, and the negatives, and g_2 = 1, p_2, p_1, or 1, and the
negatives.

But your solution has more than that because it gives

y = (5f_1 - 3f_2 + 21g_1 - g_2)/4

as a solution as well.

But that's more than the explicit equation allows.

I may be missing something, but you may have just worked backwards from
the solution for y to make your claim, or I'm missing something.

Trouble is, 4 linear equations and 4 variables give ONE solution for y,
while your claims give more than one, forcing

y = (5f_1 - 3f_2 + 21g_1 - g_2)/4

to be true, as well, as

y = (7g_1 - 3g_2 + 5f_1 - 3f_2)/4

which is odd.

It's why I decided after thinking that this method MUST lead to a
surrogate factoring solution as the only way the algebra can avoid the
contradiction is to use a surrogate factorization.

You claim otherwise with your post.

Your claims mean that 4 linear equations can be wrong.

I wonder if you just lied.


James Harris

.

Relevant Pages

  • Re: JSH: SF: Finally, surrogate factoring
    ... and with the second you would get y inside the square on the right. ... There is one explicit solution for y given by solving the 4 linear ... But from your original four linear equations we can derive ... surrogate factoring solution as the only way the algebra can avoid the ...
    (sci.math)
  • Re: JSH: SF: Finally, surrogate factoring
    ... and with the second you would get y inside the square on the right. ... So completing the square w.r.t y first yields ... Hey, I was curious to see it, figured someone could put up a solution, ... But I can also solve for y directly using the 4 linear equations, ...
    (sci.math)