Символ Лежандра

Символ Лежандра, L(a,p), определен, если a - это любое целое число, а p - простое число, большее, чем 2. Он равен 0, 1 или -1.

L(a,p) = 0, если a делится на p.

L(a,p) = 1, если a - квадратичный вычет по модулю p.

L(a,p) = -1, если a не является квадратичным вычетом по модулю p.

L(a,p) можно рассчитать следующим образом:

L(a,p) = a⁽^p^-1)/2 mod p

Или можно воспользоваться следующим алгоритмом:

Если a = 1, то L(a,p) = 1
Если a четно, то L(a,p) = L(a/2,p) *
Если a нечетно (и ? 1), то L(a,p)= L(p mod a, p)*(-1)^(a-1)(p-1)/4

Обратите внимание, что этот метод также является эффективным способом определить, является ли a квадратичным вычетом по модулю p (для простого числа p).