Legendre’s Symbol
May 1, 2012
The Legendre Symbol and its cousin the Jacobi Symbol are used in modular arithmetic to determine if a number a is a quadratic residue to the modulus m. A number a is a quadratic residue if there exists a number x such that x2 ≡ a (mod m) and is defined only when a and m are co-prime. For instance, a2 (mod 7) for a from 0 to 6 is the list 02 (mod 7) = 0, 12 (mod 7) = 1, 22 (mod 7) = 4, 32 (mod 7) = 2, 42 (mod 7) = 2, 52 (mod 7) = 4, and 62 (mod 7) = 1, so the quadratic residues of 7 are 1, 2 and 4 (0 is excluded because it isn’t co-prime to 7). The jacobi symbol considers any odd modulus; the legendre symbol is limited to odd prime moduli. The symbols are usually written in parentheses with a over m, like this: 
The legendre/jacobi symbol can be calculated according to the following three termination rules:
1. (0 / m) = 0
2. (1 / m) = 1
3. (2 / m) = −1 if m mod 8 ∈ {3, 5} or 1 if m mod 8 ∈ {1, 7}
and the following three reduction rules:
4. [reducing factors of 2] (2a / m) = (2 / m) × (a / m)
5. [reducing modulo m] (a / m) = (a (mod m) / m) if a ≥ m or a < 0
6. [reducing odd co-primes a and m] (a /m) = −(m / a) if a ≡ m ≡ 3 (mod 4), or (m / a) otherwise
Thus, the legendre/jacobi symbol is 1 if a is a quadratic residue, -1 if a is not a quadratic residue, and 0 if a and m are not co-prime.
Our various prime-number programs have used a definition of the legendre/jacobi symbol that doesn’t work; for some values of a and m it returned wrong results, and for other values of a and m it entered an infinite loop. This exercise fixes the problem.
Your task is to write a function that calculates the legendre/jacobi symbol using the rules given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
I first tried translating this to a completely iterative algorithm, but it was becoming a mess.. I also couldn’t think of a better way to reduce the rule 3 logic.
use strict; use warnings; sub reduce { my ($p, $a, $m) = (1, @_); if ($a > 2) { # rule 4 $p *= reduce(2, $m) * reduce($a / 2, $m) unless $a & 1; # rule 6 $p *= -reduce(-$m, $a) if $a % 4 == 3 and $m % 4 == 3; } # rules 1 and 2 $p *= $a unless $a >> 1; # rule 3 if (2 == $a) { my $mod8 = $m % 8; $p *= -1 if 3 == $mod8 or 5 == $mod8; $p *= 1 if 1 == $mod8 or 7 == $mod8; } return $p; } sub legendre($) { my ($a, $m) = @{(shift)}; die "modulus must be prime positive integer$/" unless int($m) == $m and $m > 0 and $m & 1; # need to also verify $m is prime, but meh # rule 5 my $n = $a % $m; print "($a / $m) = ".reduce($n, $m).$/; } legendre(\@ARGV);Ardnew: the usual iterative solution looks like this:
a = a mod m;t = 1;
while (a != 0) {
while (a even) {
a = a / 2;
if (m mod 8 in {3,5}) t = -t;
}
(a,m) = (m,a) // swap variables
if (a === m === 3 (mod 4)) t = -t
a = a mod m;
}
if (m == 1) return t;
return 0;
very nice! always seems so simple once you see the answer…
also, there’s a bug in my code that doesn’t reapply rule 5 when rule 6 is evaluated. I’m not familiar enough with the math to prove this behavior is incorrect though
In a private email, Mike pointed out that I missed the
elseclause in Rule 6. It is now fixed.An iterative Python version:
def jacobi(n, m): j = 1 # rule 5 n %= m while n: # rules 3 and 4 t = 0 while not n & 1: n /= 2 t += 1 if t&1 and m%8 in (3, 5): j = -j # rule 6 if (n % 4 == m % 4 == 3): j = -j # rules 5 and 6 n, m = m % n, n return j if m == 1 else 0Mike, a couple comments:
a) I love that 3-way equality condition in rule 6. Never seen that before :)
b) Can you explain the behavior of the expression: “if t&1 and m%8 in (3, 5)”
And Mr. programmingpraxis (i assume that is your real name), a question:
Is rule 5 even a necessary reduction? I’m beginning to think its there merely for computational optimization
Oops, I was caught up in that equality expression, disregard comment b), Mike.
@ardnew,
The ability to chain relational operators is a nice feature of Python syntax. It compiles to a series of 2-way relational tests ‘and’ed together. “if n%4 == m%4 == 3:” compiles like “if n%4 == m%4 and m%4 == 3:”, but the m%4 is only evaluated once. It is handy when you want to check if a value is between two limits, like “if lowerbound <= x = y <= z:" in a previous exercise to determine that y was no larger than either x or z. You can also chain any number together: "a c == d …”
Rule 5 is the only way to reduce ‘a’ when it’s not even.
Oops, wordpress ate some of my relational operators as html tags. Should be:
The ability to chain relational operators is a nice feature of Python syntax. It compiles to a series of 2-way relational tests ‘and’ed together. “if n%4 == m%4 == 3:” compiles like “if n%4 == m%4 and m%4 == 3:”, but the m%4 is only evaluated once. It is handy when you want to check if a value is between two limits, like “if lowerbound <= x < upperbound:". I used something like "if x >= y <= z:" in a previous exercise to determine that y was no larger than either x or z. You can also chain any number together: "a < b > c == d …”
Rule 5 is the only way to reduce ‘a’ when it’s not even.
Since Mike already did an iterative Python version, here’s a straight translation of the rules to Haskell:
jacobi :: Integer -> Integer -> Integer jacobi a m | even m = error "m must be odd." | a == 0 = 0 | a == 1 = 1 | a == 2 = if (m `mod` 8) `elem` [3, 5] then -1 else 1 | even a = jacobi 2 m * jacobi (a `div` 2) m | a >= m = jacobi (a `mod` m) m | otherwise = let j = jacobi m a in if (a `mod` 4 == 3) && (m `mod` 4 == 3) then -j else jNot the most efficient solution, probably. Happy to see another math exercise, though! (even though it should be titled “Jacobi’s Symbol,” since we don’t know m is prime)
As a preprocessing step, I think rule 5 needs to be applied if a (7 / -1) by rule 6 (the only rule that could apply
(7 / -1) => (0 / -1) by rule 5
(0 / -1) => 0 by rule 1
However, (-1 / 7) = -1 according to the programmingpraxis solution.
If rule 5 is applied first, then:
(-1 / 7) => (6 / 7) by rule 5
(6 / 7) => (2 / 7) * (3 / 7) => (3 / 7) => -(7 / 3) => -(1 / 3) => -1 by rules 4, 3, 6, 5, and 2, respectively
I did it again. (Maybe I need an option to preview a post)
The previous post should be:
As a preprocessing step, I think rule 5 needs to be applied if a < 0.
For example:
(-1 / 7) => (7 / -1) by rule 6 (the only rule that could apply)
(7 / -1) => (0 / -1) by rule 5
(0 / -1) => 0 by rule 1
However, (-1 / 7) = -1 according to the programmingpraxis solution.
If rule 5 is applied first, then:
(-1 / 7) => (6 / 7) by rule 5
(6 / 7) => (2 / 7) * (3 / 7) => (3 / 7) => -(7 / 3) => -(1 / 3) => -1; by rules 4, 3, 6, 5, and 2, respectively.
The jacobi symbol for (-1 7) is -1. Wolfram Alpha agrees.
In arithmetic mod m, the only numbers allowed are 0 to m-1 inclusive. There are no negative numbers. So any time you see a negative number you have to add m repeatedly until it is in the range 0 to m-1 inclusive. So yes, Rule 5 applies whenever a<0. I'll edit the rule.