20100508, 18:36  #1 
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 20100508 at 18:37 
20100508, 22:23  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×311 Posts 
Quote:
"Euler's Criterion" and: "Quadratic Reciprocity" 

20100509, 03:13  #3 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
has solution for if and only if
, if p is prime, a > p If then i.e. 1 if p = 1 or 7 (mod 8), 1 if p = 3 or 5 (mod 8) i.e. if atleast m or n = 1 (mod 4) if both of m, n = 3 (mod 4) 
20100509, 03:27  #4 
Apr 2010
19 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
question: decidability for quadratic residues modulo a composite  LaurV  Math  18  20170916 14:47 
quadratic residues  zippy  Math  6  20150720 13:09 
Fun with LL residues  NBtarheel_33  Data  19  20150421 16:02 
residues and non residues of general quadratic congruences  smslca  Math  0  20121012 06:42 
weird residues  ATH  Data  2  20120814 02:25 