User Name Remember Me? Password

 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
Re: quadratic residues with primes

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
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) 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 Tags primes, quadratic, residues Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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

Copyright © 2019 My Math Forum. All rights reserved.       