Friday, October 27, 2006
JSH: Why factoring idea changed
I had a simple idea for factoring which I felt really should work, and I'd done quite a bit of analysis with it. But I had this variable S, which I finally noticed took away the likelihood that the idea DID actually work.
So I thought a bit about how to get rid of it and came up with a slightly different idea:
x^2 - y^2 = 0 mod T
and
k^2 = 2xk mod T
so now it's
(x+k)^2 = y^2 + 2k^2 + nT
where I introduce n, which has to be nonzero, and you pick n and k, where the simplest thing may be to let n=-1, and then find the smallest k such that
2k^2 - T
is positive to give a small number to factor as you factor 2k^2 + nT to find y and then x.
By tossing S, I bring the variable count down and make it where the math, hopefully, will realize what your target T is, while before, with S, it could be just about anything.
So I thought a bit about how to get rid of it and came up with a slightly different idea:
x^2 - y^2 = 0 mod T
and
k^2 = 2xk mod T
so now it's
(x+k)^2 = y^2 + 2k^2 + nT
where I introduce n, which has to be nonzero, and you pick n and k, where the simplest thing may be to let n=-1, and then find the smallest k such that
2k^2 - T
is positive to give a small number to factor as you factor 2k^2 + nT to find y and then x.
By tossing S, I bring the variable count down and make it where the math, hopefully, will realize what your target T is, while before, with S, it could be just about anything.
# posted by James Harris @ 17:09 
