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