### Saturday, November 07, 2009

There is a surprisingly simple fundamental relation between factoring and quadratic residues using simple congruences.

Given a quadratic residue q modulo N, where N is a non-unit odd natural number coprime to 3, where you wish to find k, where

k^2 = q mod N

you first find T = 2q mod N, so T = 2q + jN, and j is a non-zero integer.

You next check each factorization of T to find positive f_1 and f_2 such that f_1*f_2 = T and then you get k quite simply from

k = 3^{-1}(f_1 + f_2) mod N

where for roughly 50% of cases you will get a k that will work, as a primary requirement is:

T - k^2 - f_1^2 = 0 mod N

So T - f_1^2 must be a quadratic residue modulo N, and as T = 2q mod N, you have 2q - f_1^2 must be a quadratic residue modulo N. That means, for instance, that if the first trivial factorization of T does not work, then none will, as f_1 mod N will, of course, remain the same.

So let's try it. Let N = 35, as that's simple enough, and q=29 (I'll explain how I picked it later).

Then, T = 2(29) mod 35, which is T = 23 mod 35.

The first possible T is T = 93, and it does work with f_1 = 93, and f_2 = 1 (so yes, trivial factorizations can work), as I get:

k = 3^{-1}(93 + 1) mod 35 = 12(94) mod 35 = 1128 mod 35 = 8 mod 35.

And k = 8 mod 35 is a correct answer.

And now you can see how I picked that example as knowing that 35 has 5 and 7 as factors I picked the first k coprime to 35 that would not give a perfect square:

8^2 = 29 mod 35

My first example was with k=8, using q = 29 modulo 35, as that's the first case where the quadratic residue is not a perfect square (though this method WILL solve a perfect square as well I should add) and is coprime to 35.

So now let's move k up one and do, k=9. And 81 mod 35 = 11, so q = 11 mod 35, and T = 22 mod 35, so I can try T = 57.

The trivial factorization didn't work here—which means none will—so I'll go to the non-trivial one:

f_1 = 19, and f_2 = 3, so:

k = 3^{-1}(19 + 3) mod 35 = 12(22) mod 35 = 264 mod 35 = 19 mod 35.

19^2 = 11 mod 35

so it worked! (It's so weird though watching it. Even though I know the underlying mathematics it seems like magic.)

And that is a factoring example, as I know k=9 is a solution, so I have

19^2 = 9^2 mod 35

so (19-9)(19+9) = 0 mod 35, so (10)(28) = 0 mod 35,

and you pull 5 and 7 as factors with a gcd.

THAT is how you use a method for solving quadratic residues modulo N: you find one quadratic residue and then go looking for another.

The result follows from the mathematics regarding a new way to factor I discovered that I call surrogate factoring.

To do further research into it, do a web search on: surrogate factoring

The gist of it is leveraging TWO difference of squares versus just considering one:

z^2 - y^2 = 0 mod T and x^2 - y^2 = 0 mod N

So I connect the factorization of T with the factorization of N—beautifully simple idea—which allows me to pull information about one from factoring the other, which is just really neat. I'm popularizing the result as some people have smeared me as a math crackpot, wrongfully, so I have to push results that should just excite the mathematical community on their own, which is sad.

Just some nasty people calling me names, and even beautiful mathematics has to be pushed on math people. Weird world.