Tuesday, November 11, 2008
Solving quadratic residues mod N
There is a remarkably simple yet perfect way to generally solve quadratic residues mod a non-unit natural number N, coprime to 3.
Given a quadratic residue q modulo N where N is a non-unit natural number coprime to 3, where you wish to find k, where
k^2 = q mod N
you first find
T = 2q mod N
where T = 2q + jN, and j is a non-zero integer chosen such that T mod 3 = 2.
You next check each factorization of T to find f_1 and f_2 where f_1*f_2 = T, and look for k from
k = (f_1 + f_2)/3
with 100% certainty that you will get k that will work for some factorization of T.
Example: Let q=5, N=19, then T = 10 mod 19, and T = 29, works with f_1=29 and f_2 = 1, giving
3k = 30 mod 19, and k=10.
10^2 = 5 mod 19.
The result follows from some fascinating yet trivial algebra.
Given a quadratic residue q modulo N where N is a non-unit natural number coprime to 3, where you wish to find k, where
k^2 = q mod N
you first find
T = 2q mod N
where T = 2q + jN, and j is a non-zero integer chosen such that T mod 3 = 2.
You next check each factorization of T to find f_1 and f_2 where f_1*f_2 = T, and look for k from
k = (f_1 + f_2)/3
with 100% certainty that you will get k that will work for some factorization of T.
Example: Let q=5, N=19, then T = 10 mod 19, and T = 29, works with f_1=29 and f_2 = 1, giving
3k = 30 mod 19, and k=10.
10^2 = 5 mod 19.
The result follows from some fascinating yet trivial algebra.
# posted by James Harris @ 20:56 
