### 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.