My Math Forum quadratic residues with primes

 Number Theory Number Theory Math Forum

 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: p-1 = x then calculate all the x^2 mod p until you reach p-1 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

Quote:
 Originally Posted by slippy 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.
No. The Legendre (Jacobi) symbol isn't division! It's a different operation altogether.

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
(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) and modular square roots as 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^2s-i-1 mod p is that correct ? Thanks Alex

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post zelmac Number Theory 1 December 28th, 2012 09:57 AM smslca Number Theory 5 October 12th, 2012 09:48 AM smslca Number Theory 0 October 12th, 2012 01:34 AM veronicak5678 Complex Analysis 14 February 28th, 2012 09:44 AM undefined Number Theory 2 April 1st, 2010 10:21 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top