Harristotelian Logic

I noted that you can use the result that with naturals n_1, p a prime factor of n_1, n_2,

C = n_1 + n_2, and k a difference of factors of 2*C that

(8*C + k^2) mod n_1 must be a square modulo p

and, of course, that means that it is a square modulo n_1.

So I thought to myself, hey, why not use this result to try and factor?

So I arbitrarily picked k=1, C = mT, so I'd have

sqrt(1 + 8*mT)

where T is the target to be factored, and I solved for m as a congruence relation and found that

m = (r-1)(8*T)^{-1} mod n_1

where is a square modulo n_1, or as I like to say, is a quadratic residue of n_1.

Notice here you can pick n_1 to be ANY natural number you choose. I tossed out floor(T/2) as a possibility, as, well, it was just an idea of the moment.

I also have tended to just pick r=4, because just about any n_1 will have 4 as a quadratic residue, but you can pick something else.

What the mathematics tells you is that ALL solutions for m that will give you that quadratic residue, must fit into the congruence relationship given.

But how likely are you to find a solution?

I don't know. It is possible, amazingly enough, and possibly unfortunately, that as T increases and size, and as you pick an ever large n_1, close to T, that the number of possible m's increases rapidly, as in, faster than linear.

Or, they may drop rapidly. Or, they may stay roughly the same, while the quadratic residues increase linearly. Or the number of m's may increase at roughly the same rate as the number of quadratic residues.

So the theory is not such a big deal as it's all simple.

But the practicality is in question, where maybe, if you pick n_1 correctly, and go to bigger and bigger composites, um, you may find it easier to factor than with small numbers.

So little test examples may give the wrong idea, but I'm still in guess mode.

The problem, with T = p_1 p_2, where the p's are primes, can be considered to be finding the solution set

xp_1 - yp_2 = 1

where m = xy, and it looks to me like it might go as the square, in turns of possible m's so that while you increase T linearly, the number of m's that will work, increase as the square, which if true means we're screwed, and someone could figure out a way to factor with this thing, where it would actually work better with RSA sized numbers than with smaller numbers.

But I'm still just guessing and I'm not seeing posts that address the actual theoretical issues, so I think it's an open question.

Then again, I think I could be reaching, hoping a nice idea that can't be practical can be, and that instead the odds of landing on an m decrease so rapidly that they are vanishingly small with a large T, which I think is the opinion that most would think should apply.

After all, if that weren't true, then I couldn't just be chatting out a solution to the factoring problem on Usenet for DAYS, so it must not be true, right?