This is an alternative to the original Legendre Symbol (C# code)[^]. That implementation suffered from a simple, but significant, error, and significant inefficiency.
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)
throw new ArgumentOutOfRangeException("p", "p must not be < 2");
if (a == 0)
if (a == 1)
if (a % 2 == 0)
result = Legendre(a / 2, p);
if (((p * p - 1) & 8) != 0)
result = -result;
result = Legendre(p % a, a);
if (((a - 1) * (p - 1) & 4) != 0)
result = -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
- correct checking for
a == 0 (Without it, infinite recursion was possible. Try
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.