Символ Якоби: различия между версиями

 

Символ Якоби обобщает [[символ Лежандра]] на все [[нечётные числа]], большие единицы. [[Символ Кронекера — Якоби]], в свою очередь, обобщает символ Якоби на все [[целые числа]], но в практических задачах символ Якоби играет гораздо более важную роль, чем символ Кронекера — Якоби.

== Определение ==

 

:<math>\left(\frac{a}{P}\right) = \left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots\left(\frac{a}{p_n}\right) </math>,

где <math>\left(\frac{a}{p_i}\right)</math> — [[символ Лежандра|символы Лежандра]].

 

== Свойства ==

 

* [[Мультипликативная функция|Мультипликативность]]: <math>\left(\frac{ab}{P}\right) = \left(\frac{a}{P}\right) \left(\frac{b}{P}\right)</math>

* <math>\left(\frac{-1}{P}\right) = (-1)^{\frac{P-1}{2}}</math>

* <math>\left(\frac{2}{P}\right) = (-1)^{\frac{P^2-1}{8}}</math>

*Символ Якоби <math>\left(\frac{a}{P}\right)</math> равен [[знак перестановки|знаку перестановки]] [[приведённая система вычетов|приведённой системы вычетов]] по модулю <math>P</math>, которая задается как умножение элементов этой группы на <math>a</math> (где <math>a</math> обязательно взаимно просто с <math>P</math>).

 

 

 

Символ Якоби практически никода не вычисляют по определению. Чаще всего для вычисления используют свойства символа Якоби, главным образом — квадратичный закон взаимности.

Более того, несмотря на то, что символ Якоби является обобщением [[символ Лежандра|символа Лежандра]] и определяется через него, чаще именно символ Лежандра вычисляют с помощью символа Якоби, а не наоборот. См. [[#Пример|Пример]]

 

 

В отличие от символа Лежандра, символ Якоби нельзя напрямую использовать для проверки разрешимости квадратичного сравнения. То есть, если задано сравнение

Но если <math>\left(\frac{a}{n}\right)=-1</math>, то сравнение (1) не имеет решений.

 

 

В общем случае неверно, что для символа Якоби выполняется то же условие, что и для символа Лежандра:

Данное свойство используется в вероятностном [[алгоритм Соловея-Штрассена|тесте Соловея-Штрассена]] на простоту. В этом алгоритме выбираются случайные числа ''a'' и для них проверяется условие (2). Если находится свидетель непростоты, то доказано, что число ''P'' – составное. В противном случае говорят, что ''P'' — простое с некоторой [[вероятность]]ю.

 

 

Главным образом, символ Якоби используется для быстрого вычисления [[Символ Лежандра|символа Лежандра]].

Символ Якоби используется в некоторых [[тест простоты|тестах на простоту]], например, в [[(N+1) – метод проверки простоты|(N+1) – методах]] и, [[#Особенность, используемая в тестах простоты|как уже было сказано]], в [[алгоритм Соловея — Штрассена|тесте Соловея — Штрассена]].

 

 

 

Ключевое используемое при вычислении свойство символа Якоби — квадратичный закон взаимности. Благодаря нему алгоритм похож на [[алгоритм Евклида]] нахождения [[наибольший общий делитель|наибольшего общего делителя]] двух чисел, в котором тоже аргументы на каждом шаге меняются местами. Аналогично [[алгоритм Евклида|алгоритму Евклида]], при перестановке аргументов больший заменяется на остаток от деления на меньший. Это возможно благодаря [[Периодическая функция|периодичности]] символа Якоби. Однако, поскольку символ Якоби определён только при условии нечётности второго аргумента, то до перестановки выделяется чётная часть первого аргумента.

 

 

'''Входные данные:''' ''a'' — целое число, ''b'' — натуральное, нечётное, больше единицы..

'''6''' ''(выход из алгоритма?).'' Если ''a''≠0, то идти на шаг 4, иначе выйти из алгоритма с ответом '''r'''.

 

 

В алгоритме везде берётся наименьший положительный вычет (то есть остаток от деления).

Сложность алгоритма равна <math>O(\log{a}\cdot\log{b})</math> битовых операций.

 

 

Вычисление символа Лежандра с помощью символа Якоби:

 

 

 

* {{книга

[[it:Simbolo di Jacobi]]

[[km:សញ្ញាយ៉ាកូប៊ី]]

[[nl:Jacobi-symbool]]

[[pl:Symbol Jacobiego]]