Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Resolving quadratic residues
Posted:
Nov 7, 2009 3:13 PM
|
|
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.
James Harris
|
|
|
|
