Символ Лежандра, Ца,р), определен, если а - это любое целое число, а р - простое число, большее, чем 2. Он равен 0, 1 или-1.
Ца,р) = 0, если а делится на р.
Ца,р) = 1, если а - квадратичный вычет по модулю р.
Ца,р) = -1, если а не является квадратичным вычетом по модулю р.
Ца,р) можно рассчитать следующим образом:
Ца,р) = ^"1)/2 mod p
Или можно воспользоваться следующим алгоритмом:
1. Еслиа= 1,тоЦа,/>) = 1
2. Если а четно, то Ца,р) = Ца/2,р) * (-I)**2-1''8
3. Если а нечетно (и Ф 1), то Ца,р)= Up mod а, р)*(-1)^^'4
Обратите внимание, что этот метод также является эффективным способом определить, является ли а квадратичным вычетом по модулю р (для простого числа/;).