mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-05-08, 18:36   #1
Romulas
 
Apr 2010

19 Posts
Default 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 2010-05-08 at 18:37
Romulas is offline   Reply With Quote
Old 2010-05-08, 22:23   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts
Default

Quote:
Originally Posted by Romulas View Post
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.
Look up:

"Euler's Criterion"

and:

"Quadratic Reciprocity"
R.D. Silverman is offline   Reply With Quote
Old 2010-05-09, 03:13   #3
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

x^2 = a\ (mod\ p) has solution for x if and only if \left( \frac{a}{p} \right) = 1

\left( \frac{a}{p} \right) = a^{p-1 \over 2}\ (mod\ p)

\left( \frac{a}{p} \right) = \left( \frac{p-a}{p} \right), if p is prime, a > p

\left( \frac{a}{mn} \right) = \left( \frac{a}{m} \right) * \left( \frac{a}{n} \right)

\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) * \left(  \frac{b}{p} \right)

If n = p_1^{c_1}*p_2^{c_2}*p_3^{c_3}*...*p_k^{c^k} then
\left( \frac{a}{n} \right) = \left( \frac{a}{p_1} \right)^{c_1}*\left( \frac{a}{p_2} \right)^{c_2}*\left( \frac{a}{p_3} \right)^{c_3}*...*\left( \frac{a}{p_k} \right)^{c_k}

\left( \frac{1}{p} \right) = 1

\left( \frac{-1}{p} \right) = (-1)^{p-1 \over 2}

\left( \frac{2}{p} \right) = (-1)^{p^2-1 \over 8}
i.e. 1 if p = 1 or 7 (mod 8), -1 if p = 3 or 5 (mod 8)

\left( \frac{m}{n} \right) * \left( \frac{n}{m} \right) = (-1)^{(m-1)(n-1) \over 4}
i.e. \left( \frac{m}{n} \right) = \left( \frac{n}{m} \right) if atleast m or n = 1 (mod 4)
\left( \frac{m}{n} \right) = -\left( \frac{n}{m} \right) if both of m, n = 3 (mod 4)
Raman is offline   Reply With Quote
Old 2010-05-09, 03:27   #4
Romulas
 
Apr 2010

19 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Look up:

"Euler's Criterion"

and:

"Quadratic Reciprocity"
Great! That works perfectly! Thanks for the sources!
Romulas is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
question: decidability for quadratic residues modulo a composite LaurV Math 18 2017-09-16 14:47
quadratic residues zippy Math 6 2015-07-20 13:09
Fun with LL residues NBtarheel_33 Data 19 2015-04-21 16:02
residues and non residues of general quadratic congruences smslca Math 0 2012-10-12 06:42
weird residues ATH Data 2 2012-08-14 02:25

All times are UTC. The time now is 01:53.


Thu Aug 18 01:53:17 UTC 2022 up 41 days, 20:40, 1 user, load averages: 2.39, 2.06, 1.67

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔