Символ Якоби
Пусть P — нечётное, большее единицы число и Свойства. § Мультипликативность: § В частности, § Периодичность: если § § § § § Если Q — нечётное натуральное число, взаимно простое с P, то § В частности, если P и Q взаимно простые и нечётные, то § Символ Якоби Применение. Главным образом, символ Якоби используется для быстрого вычисления символа Лежандра. Символ Лежандра, в свою очередь, необходим для проверки разрешимости квадратичного сравнения по модулю простого числа. Но считать его по определению (то есть вычислять Символ Якоби используется в некоторых тестах на простоту, например, в (N+1)-методах и, как уже было сказано, в тесте Соловея — Штрассена. Алгоритм.
|
— его разложение на простые множители (среди 
могут быть равные). Тогда для произвольного целого числа a символ Якоби определяется равенством: 
где 
— символы Лежандра. По определению считаем, что 
для всех a.
.
.
, то
— аналог квадратичного закона взаимности.
.
равен знаку перестановки приведённой системы вычетов по модулю P, которая задаётся как умножение элементов этой группы на a (где обязательно взаимно просто с P).
) — достаточно долгая по времени процедура. С помощью алгоритма быстрого возведения в степень это делается за O (log3 p) битовых операций (если не использовать быстрое умножение и деление). А вычисление символа Якоби требует только O (log2 p) битовых операций.
