My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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:

p-1 = x
then calculate all the x^2 mod p until you reach p-1

what next ?

Thanks
Alex
slippy is offline  
 
October 18th, 2009, 09:18 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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
slippy is offline  
October 19th, 2009, 02:49 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
slippy is offline  
October 21st, 2009, 06:03 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
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
CRGreathouse is offline  
October 21st, 2009, 06:48 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
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))
CRGreathouse is offline  
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
slippy is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.