## 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 *x*^{2} ≡ *a* (mod *m*) and is defined only when *a* and *m* are co-prime. For instance, *a*^{2} (mod 7) for *a* from 0 to 6 is the list 0^{2} (mod 7) = 0, 1^{2} (mod 7) = 1, 2^{2} (mod 7) = 4, 3^{2} (mod 7) = 2, 4^{2} (mod 7) = 2, 5^{2} (mod 7) = 4, and 6^{2} (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: . Sometimes the symbol is written with a horizontal rule between the *a* and *m*, and sometimes it is written on a single line as (*a* / *m*).

The legendre/jacobi symbol can be calculated according to the following three termination rules:

1. (0 /

m) = 02. (1 /

m) = 13. (2 /

m) = −1 ifmmod 8 ∈ {3, 5} or 1 ifmmod 8 ∈ {1, 7}

and the following three reduction rules:

4. [reducing factors of 2] (2

a/m) = (2 /m) × (a/m)5. [reducing modulo

m] (a/m) = (a(modm) /m) ifa≥mora< 06. [reducing odd co-primes

aandm] (a/m) = −(m/a) ifa≡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.

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.

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

`else`

clause in Rule 6. It is now fixed.An iterative Python version:

Mike, 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:

Not 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.