## Introduction

This is an alternative to the original Legendre Symbol (C# code)[^]. That implementation suffered from a simple, but significant, error, and significant inefficiency.

## Background

See the Wikipedia article "Legendre symbol"[^] for the definition and theory behind this.

## Using the code

Here is my implementation of the method:

public static int Legendre(int a, int p) { if (p < 2) // prime test is expensive. throw new ArgumentOutOfRangeException("p", "p must not be < 2"); if (a == 0) { return 0; } if (a == 1) { return 1; } int result; if (a % 2 == 0) { result = Legendre(a / 2, p); if (((p * p - 1) & 8) != 0) // instead of dividing by 8, shift the mask bit { result = -result; } } else { result = Legendre(p % a, a); if (((a - 1) * (p - 1) & 4) != 0) // instead of dividing by 4, shift the mask bit { result = -result; } } return result; }

Compared to the original this has added:

`static`

declaration because it is self-contained (doesn't depend on any class instance values)- initial "validation" of
`p`

- correct checking for
`a == 0`

(Without it, infinite recursion was possible. Try`L(3,3)`

.)

Most significantly, the computationally expensive use of `Math.Pow()`

to set the sign of the result has been replaced with all integer operations. This implementation is about 7 times faster than the original tip.

The attached zip file has both implementations, with code for timing and verification of identical results on about 16 million test cases.

## Points of Interest

In the original sign manpulation code -1 was being raised to an integer power to be either +1 or -1, and then multiplied by the recursion result to conditionally change the sign of that result. It is only necessary to change the sign if that integer power is odd so a lowest-order bit test will do the job. Since in the original sign manipulation code cases the factors were divided by 8 or 4 (both powers of 2) before being used, the equivalent to the division-then-bit-test is just to shift the bit being tested and avoid the division entirely.