Quadratic Residues

Romulas · 2010-05-08, 18:36

So, I'm trying to come up with an efficient algorithm for calculating the Legendre Symbol, which is defined as follows:

Legendre(a, p) where p is prime is 0 when a = 0 (mod p), 1 when a is a quadratic residue (mod p), and -1 when a is a quadratic nonresidue (mod p).

I'm a little confused about quadratic residues and how to efficiently calculate them on a computer. I can calculate whether a number is a quadratic residue (mod a prime), but I'm struggling with implementing an algorithm to do this.

R.D. Silverman · 2010-05-08, 22:23

Quote:

Originally Posted by Romulas

So, I'm trying to come up with an efficient algorithm for calculating the Legendre Symbol, which is defined as follows:

Legendre(a, p) where p is prime is 0 when a = 0 (mod p), 1 when a is a quadratic residue (mod p), and -1 when a is a quadratic nonresidue (mod p).

I'm a little confused about quadratic residues and how to efficiently calculate them on a computer. I can calculate whether a number is a quadratic residue (mod a prime), but I'm struggling with implementing an algorithm to do this.

Look up:

"Euler's Criterion"

and:

"Quadratic Reciprocity"

Raman · 2010-05-09, 03:13

$x^2 = a\ (mod\ p)$ has solution for $x$ if and only if $\left( \frac{a}{p} \right) = 1$

$\left( \frac{a}{p} \right) = a^{p-1 \over 2}\ (mod\ p)$

$\left( \frac{a}{p} \right) = \left( \frac{p-a}{p} \right)$ , if p is prime, a > p

$\left( \frac{a}{mn} \right) = \left( \frac{a}{m} \right) * \left( \frac{a}{n} \right)$

$\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) * \left( \frac{b}{p} \right)$

If $n = p_1^{c_1}*p_2^{c_2}*p_3^{c_3}*...*p_k^{c^k}$ then
$\left( \frac{a}{n} \right) = \left( \frac{a}{p_1} \right)^{c_1}*\left( \frac{a}{p_2} \right)^{c_2}*\left( \frac{a}{p_3} \right)^{c_3}*...*\left( \frac{a}{p_k} \right)^{c_k}$

$\left( \frac{1}{p} \right) = 1$

$\left( \frac{-1}{p} \right) = (-1)^{p-1 \over 2}$

$\left( \frac{2}{p} \right) = (-1)^{p^2-1 \over 8}$
i.e. 1 if p = 1 or 7 (mod 8), -1 if p = 3 or 5 (mod 8)

$\left( \frac{m}{n} \right) * \left( \frac{n}{m} \right) = (-1)^{(m-1)(n-1) \over 4}$
i.e. $\left( \frac{m}{n} \right) = \left( \frac{n}{m} \right)$ if atleast m or n = 1 (mod 4)
$\left( \frac{m}{n} \right) = -\left( \frac{n}{m} \right)$ if both of m, n = 3 (mod 4)

Romulas · 2010-05-09, 03:27

Quote:

Originally Posted by R.D. Silverman

Look up:

"Euler's Criterion"

and:

"Quadratic Reciprocity"

Great! That works perfectly! Thanks for the sources!

2010-05-08, 18:36	#1
Romulas Apr 2010 19 Posts	Quadratic Residues So, I'm trying to come up with an efficient algorithm for calculating the Legendre Symbol, which is defined as follows: Legendre(a, p) where p is prime is 0 when a = 0 (mod p), 1 when a is a quadratic residue (mod p), and -1 when a is a quadratic nonresidue (mod p). I'm a little confused about quadratic residues and how to efficiently calculate them on a computer. I can calculate whether a number is a quadratic residue (mod a prime), but I'm struggling with implementing an algorithm to do this. Last fiddled with by Romulas on 2010-05-08 at 18:37

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
question: decidability for quadratic residues modulo a composite	LaurV	Math	18	2017-09-16 14:47
quadratic residues	zippy	Math	6	2015-07-20 13:09
Fun with LL residues	NBtarheel_33	Data	19	2015-04-21 16:02
residues and non residues of general quadratic congruences	smslca	Math	0	2012-10-12 06:42
weird residues	ATH	Data	2	2012-08-14 02:25

2010-05-09, 03:13	#3
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts	$x^2 = a\ (mod\ p)$ has solution for $x$ if and only if $\left( \frac{a}{p} \right) = 1$ $\left( \frac{a}{p} \right) = a^{p-1 \over 2}\ (mod\ p)$ $\left( \frac{a}{p} \right) = \left( \frac{p-a}{p} \right)$ , if p is prime, a > p $\left( \frac{a}{mn} \right) = \left( \frac{a}{m} \right) * \left( \frac{a}{n} \right)$ $\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) * \left( \frac{b}{p} \right)$ If $n = p_1^{c_1}p_2^{c_2}p_3^{c_3}...p_k^{c^k}$ then $\left( \frac{a}{n} \right) = \left( \frac{a}{p_1} \right)^{c_1}\left( \frac{a}{p_2} \right)^{c_2}\left( \frac{a}{p_3} \right)^{c_3}...\left( \frac{a}{p_k} \right)^{c_k}$ $\left( \frac{1}{p} \right) = 1$ $\left( \frac{-1}{p} \right) = (-1)^{p-1 \over 2}$ $\left( \frac{2}{p} \right) = (-1)^{p^2-1 \over 8}$ i.e. 1 if p = 1 or 7 (mod 8), -1 if p = 3 or 5 (mod 8) $\left( \frac{m}{n} \right) * \left( \frac{n}{m} \right) = (-1)^{(m-1)(n-1) \over 4}$ i.e. $\left( \frac{m}{n} \right) = \left( \frac{n}{m} \right)$ if atleast m or n = 1 (mod 4) $\left( \frac{m}{n} \right) = -\left( \frac{n}{m} \right)$ if both of m, n = 3 (mod 4)