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