Thursday, February 21, 2008
JSH: Finding k
Surprising answer with surrogate factoring that focuses on finding k, and leverages a rather intriguingly simple little result to factor.
As consider
2x = k + 3r
when
z^2 = y^2 + T
where T is the target to be factored, is odd and coprime to 3, and T mod 3 = 2, as then z must have 3 as a factor, so
z = x+k
gives
x^2 + 2xk + k^2 = y^2 + T
which is x^2 = y^2 + T - 2xk - k^2, and I can substitute out 2x, to get
x^2 = y^2 + T - 2k^2 - 3kr
and that's where a nifty thing pops in, as, you want r=0, but in general, r will be NEGATIVE if you start with the optimal k when r=0 and move about modulo 6, as that k will be even. That's because you'd have
x^2 = y^2 + T - 2(k+6j)^2 - 3(k+6j)r
and if you have positive k (no reason to use negative) and try to move with positive j, then r will be negative, and even if you move with negative j, the 36j^2 term will tend to dominate, forcing r to be negative to compensate.
So r = 0 should be near the value at which abs(T-2k^2) is a minimum.
Trouble is, if you continue the analysis you find that k at that point is the minimum that might work—remember k is positive—but the actual k MUST be within k/6 steps from that value.
But it gives you a sense of what is possible, just with p=3.
I generalized to p odd prime though, but found that it's still important to have z with 3 as a factor, but then you have as a crucial requirement:
k^2 = (nT)(2)^{-1} mod p
so you need a prime for which k exists, and then you find a maximal k modulo that prime, as the same argument above works, except now you'd have
2x = k + pr
and you have a solution within k/(2p) steps from the maximal k.
If T mod 3 = 2, then you'd use n=1, else you'd use n=5 or maybe 2, I'm still not sure, to force nT mod 3 = 2, as there is a crucial requirement that
z = 3x
so z has to have 3 as a factor.
Oddly enough then for me, after over four years of trying to find an alternate factoring method with a concept I call surrogate factoring it all depended on this little thing that with
x^2 = y^2 + T - 2(k+6j)^2 - 3(k+6j)r
the j^2 will tend to dominate as you move around the correct value, which forces r to be negative to compensate.
That is just so amazing to me. How such a little thing is so important.
Without that, there'd be no clue about how to get close to k, and best you could loop through searching modulo p, which is what I worked at before, but the other crucial thing was realizing that
k^2 = (nT)(2)^{-1} mod p
was the REALLY important way to go as generalizing I used a variable I call α, but it turns out that with the generalization
z = (1+2α^2)x
and it's just easier to force z divisible by 3 than it is some of the other values that can be, like 19, or 73.
All easy math, and easy to play with thankfully. Something of a subtle result though that requires you just do this odd thing of looking at
2x = k + pr
along with z = x+k, and z^2 = y^2 + nT, and then it's easy, as long as you do all those things and can argue it out for months until it all comes together.
Wow. Cool. What a result.
As consider
2x = k + 3r
when
z^2 = y^2 + T
where T is the target to be factored, is odd and coprime to 3, and T mod 3 = 2, as then z must have 3 as a factor, so
z = x+k
gives
x^2 + 2xk + k^2 = y^2 + T
which is x^2 = y^2 + T - 2xk - k^2, and I can substitute out 2x, to get
x^2 = y^2 + T - 2k^2 - 3kr
and that's where a nifty thing pops in, as, you want r=0, but in general, r will be NEGATIVE if you start with the optimal k when r=0 and move about modulo 6, as that k will be even. That's because you'd have
x^2 = y^2 + T - 2(k+6j)^2 - 3(k+6j)r
and if you have positive k (no reason to use negative) and try to move with positive j, then r will be negative, and even if you move with negative j, the 36j^2 term will tend to dominate, forcing r to be negative to compensate.
So r = 0 should be near the value at which abs(T-2k^2) is a minimum.
Trouble is, if you continue the analysis you find that k at that point is the minimum that might work—remember k is positive—but the actual k MUST be within k/6 steps from that value.
But it gives you a sense of what is possible, just with p=3.
I generalized to p odd prime though, but found that it's still important to have z with 3 as a factor, but then you have as a crucial requirement:
k^2 = (nT)(2)^{-1} mod p
so you need a prime for which k exists, and then you find a maximal k modulo that prime, as the same argument above works, except now you'd have
2x = k + pr
and you have a solution within k/(2p) steps from the maximal k.
If T mod 3 = 2, then you'd use n=1, else you'd use n=5 or maybe 2, I'm still not sure, to force nT mod 3 = 2, as there is a crucial requirement that
z = 3x
so z has to have 3 as a factor.
Oddly enough then for me, after over four years of trying to find an alternate factoring method with a concept I call surrogate factoring it all depended on this little thing that with
x^2 = y^2 + T - 2(k+6j)^2 - 3(k+6j)r
the j^2 will tend to dominate as you move around the correct value, which forces r to be negative to compensate.
That is just so amazing to me. How such a little thing is so important.
Without that, there'd be no clue about how to get close to k, and best you could loop through searching modulo p, which is what I worked at before, but the other crucial thing was realizing that
k^2 = (nT)(2)^{-1} mod p
was the REALLY important way to go as generalizing I used a variable I call α, but it turns out that with the generalization
z = (1+2α^2)x
and it's just easier to force z divisible by 3 than it is some of the other values that can be, like 19, or 73.
All easy math, and easy to play with thankfully. Something of a subtle result though that requires you just do this odd thing of looking at
2x = k + pr
along with z = x+k, and z^2 = y^2 + nT, and then it's easy, as long as you do all those things and can argue it out for months until it all comes together.
Wow. Cool. What a result.
# posted by James Harris @ 00:42 
