Sunday, March 02, 2008


JSH: z constraint valuable?

I just really noticed and focused on a result I kind of thought of as minor that comes out of my surrogate factoring research which I'm now wondering if it might not be a breakthrough result.


z^2 = y^2 + nT

and nT NOT a perfect square, I have that

z = (1 + 2α^2)k/(2α)

where k is just some non-zero integer, the crucial result is that z must have 1 + 2α^2 as a factor for some non-zero α that is an integer.

I know it doesn't work if nT is a square—which is of course a trivial case but still—though I'm not sure why.

A key underlying equation is

(α^2+1)k^2 + p(r_1 + kr_2) = nT

where to get the result I'm setting r_2 = 0, so r_1 will exist as long as

(α^2+1)k^2 = nT mod p

where p is an odd prime.

But I know that won't happen regardless of the prime p, if nT is a perfect square as I have an easy counterexample:

5^2 = 4^2 + 3^2

if nT = 16 or nT = 9.

If that result holds, regardless of nT not being a square as that's a trivial case, then it is a constraint on ALL integer factorizations that rely on congruence of squares so it'd impact the Number Field Sieve.

(I'd guess that it conceivably could impact all factoring methods known or possible, except brute force.)

<< Home

This page is powered by Blogger. Isn't yours?