Register FAQ Search Today's Posts Mark Forums Read

 2010-05-08, 18:36 #1 Romulas   Apr 2010 100112 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
2010-05-08, 22:23   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D2816 Posts

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:

 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)
2010-05-09, 03:27   #4
Romulas

Apr 2010

19 Posts

Quote:
 Originally Posted by R.D. Silverman Look up: "Euler's Criterion" and: "Quadratic Reciprocity"
Great! That works perfectly! Thanks for the sources!

 Similar Threads Thread Thread Starter Forum Replies Last Post LaurV Math 18 2017-09-16 14:47 zippy Math 6 2015-07-20 13:09 NBtarheel_33 Data 19 2015-04-21 16:02 smslca Math 0 2012-10-12 06:42 ATH Data 2 2012-08-14 02:25

All times are UTC. The time now is 21:27.

Wed Aug 10 21:27:06 UTC 2022 up 34 days, 16:14, 2 users, load averages: 2.02, 1.47, 1.34