
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
October 16th, 2009, 07:19 AM  #1 
Newbie Joined: Oct 2009 Posts: 4 Thanks: 0  quadratic residues with primes
hi, im trying to understand quadratic residues with primes i understand the first couple of stages: p1 = x then calculate all the x^2 mod p until you reach p1 what next ? Thanks Alex 
October 18th, 2009, 09:18 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: quadratic residues with primes
I don't know what you're trying to do.

October 19th, 2009, 02:25 PM  #3 
Newbie Joined: Oct 2009 Posts: 4 Thanks: 0  Re: quadratic residues with primes
sorry, i am making a program that uses shanks algorithm part of which requires me to find a integer which is the quadratic residue of the chosen prime number. hope this makes more sense Alex 
October 19th, 2009, 02:49 PM  #4 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: quadratic residues with primes
I would start with the Jacobi symbol in that case.

October 21st, 2009, 02:38 AM  #5 
Newbie Joined: Oct 2009 Posts: 4 Thanks: 0  Re: quadratic residues with primes
yes i have read about the Legendre symbol but got abit confussed with how to apply it. from the definition of it on wikipedia you divide the int over the prime but i don't understand what happens next.

October 21st, 2009, 06:03 AM  #6  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: quadratic residues with primes Quote:
Denote the Jacobi symbol as (a  b) where b is odd. Then you can calculate the Jacobi symbol with the following rules. Remove obvious factors: (you don't need to remove all factors, but do at least remove all 2s) (ab  n) = (a  n) * (b  n) (a  mn) = (a  m) * (a  n) Reduce the top mod the bottom: (a + n  n) = (a  n) Compute simple symbols: (0  n) = 0 (1  n) = 1 (2  n) = 1 if n is 1 or 7 mod 8 (2  n) = 1 if n is 3 or 5 mod 8 Use quadratic reciprocity otherwise: (a  n) = (n  a) if a is 1 mod 4 or n is 1 mod 4 (a  n) = (n  a) if a and n are both 3 mod 4  
October 21st, 2009, 06:48 AM  #7 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: quadratic residues with primes
Wait... doesn't Shanks' algorithm require a nonresidue? In that case you want (a  n) = 1 rather than 1. Also, it's worth mentioning that Pari implements the Legendre, Jacobi, and Kronecker symbols via Code: kronecker(a,n) Code: sqrt(Mod(a,p)) 
October 26th, 2009, 02:40 PM  #8 
Newbie Joined: Oct 2009 Posts: 4 Thanks: 0  Re: quadratic residues with primes
thanks for explaining residues. i have been looking at step 5 in shanks algorithm, the loop section. i = (r^2)*n^1 mod 1 until the result is 1 if i = 0 return r else put r' back though the loop r' = r*v^2si1 mod p is that correct ? Thanks Alex 

Tags 
primes, quadratic, residues 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
residues modulo 36  zelmac  Number Theory  1  December 28th, 2012 09:57 AM 
residues and non residues of general quadratic congruences  smslca  Number Theory  5  October 12th, 2012 09:48 AM 
fpt problem in quadratic residues  smslca  Number Theory  0  October 12th, 2012 01:34 AM 
Residues  veronicak5678  Complex Analysis  14  February 28th, 2012 09:44 AM 
Trivial quadratic residues for prime powers  undefined  Number Theory  2  April 1st, 2010 10:21 PM 