mersenneforum.org > Math Quadratic Residues
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2010-05-08, 18:36 #1 Romulas   Apr 2010 19 Posts 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
2010-05-08, 22:23   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

746010 Posts

Quote:
 Originally Posted by Romulas 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:

 2010-05-09, 03:13 #3 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts $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)
2010-05-09, 03:27   #4
Romulas

Apr 2010

19 Posts

Quote:
 Originally Posted by R.D. Silverman Look up: "Euler's Criterion" and: "Quadratic Reciprocity"
Great! That works perfectly! Thanks for the sources!

 Similar Threads Thread Thread Starter Forum Replies Last Post LaurV Math 18 2017-09-16 14:47 zippy Math 6 2015-07-20 13:09 NBtarheel_33 Data 19 2015-04-21 16:02 smslca Math 0 2012-10-12 06:42 ATH Data 2 2012-08-14 02:25

All times are UTC. The time now is 12:14.

Wed Jul 6 12:14:38 UTC 2022 up 83 days, 10:15, 0 users, load averages: 0.88, 1.06, 1.27

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.

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