Символ Якобі

Карл Густав Якоб Якобі (1804-1851).

Символ Якобі - теоретико-числова функція двох аргументів, введена К. Якобі в 1837. Є квадратичним характером в кільці лишків.

Символ Якобі узагальнює символ Лежандра на всі непарні числа, більші одиниці. Символ Кронекера - Якобі, в свою чергу, узагальнює символ Якобі на всі цілі числа, але в практичних завданнях символ Якобі грає набагато важливішу роль, ніж символ Кронекера - Якобі.


1. Визначення

Нехай P - непарне, більше одиниці число і P = p_1p_2 \ ldots p_n - Його розкладання на прості множники (серед p_1, \; \ ldots, \; p_n можуть бути рівні). Тоді для довільного цілого числа a символ Якобі визначається рівністю:

де \ Left (\ frac {a} {p_i} \ right) - символи Лежандра.

За визначенням вважаємо, що \ Left (\ frac {a} {1} \ right) = 1 для всіх a .


2. Властивості

Значення символу Якобі для аргументів від 1 до 100.

3. Важливі зауваження

3.1. Про обчислення

Символ Якобі практично ніколи не обчислюють за визначенням. Найчастіше для обчислення використовують властивості символу Якобі, головним чином - квадратичний закон взаємності.

Більш того, незважаючи на те, що символ Якобі є узагальненням символу Лежандра і визначається через нього, частіше саме символ Лежандра обчислюють за допомогою символу Якобі, а не навпаки. Див Приклад

3.2. Про зв'язок з квадратичних порівняннями

На відміну від символу Лежандра, символ Якобі не можна безпосередньо використовувати для перевірки можливості розв'язання квадратичного порівняння. Тобто, якщо задано порівняння

x ^ 2 \ equiv a \ mod n, ((1))

то рівність одиниці символу Якобі \ Left (\ frac {a} {n} \ right) зовсім не означає, що дане порівняння вирішуваний. Наприклад, \ Left (\ frac {2} {15} \ right) = (-1) ^ {28} = 1 , Але порівняння x ^ 2 \ equiv 2 \ mod {15} не має рішень (можна перевірити перебором).

Але якщо \ Left (\ frac {a} {n} \ right) = -1 , То порівняння (1) не має рішень.


3.3. Особливість, використовувана в тестах простоти

У загальному випадку невірно, що для символу Якобі виконується той же умова, що і для символу Лежандра:

\ Left (\ frac {a} {P} \ right) \ equiv a ^ {\ frac {P-1} {2}} \ mod P. ((2))

Наприклад,

При цьому 7 ^ {\ frac {15-1} {2}} \ equiv 7 ^ 7 \ equiv 13 \ mod {15}. Числа a , Взаємно прості з P , Для яких не виконана умова (2), називаються ейлерова свідками непростота числа P (Оскільки для простого P умова (2) виконано).

Якщо P - складене число, то таке число a , Для якого умова (2) виконано, називають брехуном для тесту Ейлера.

Доведено, що для будь-якого складового P Тобто не більше P / 2 брехунів, різних по модулю P .

Дана властивість використовується в імовірнісному тесті Соловея - штрассе на простоту. У цьому алгоритмі вибираються випадкові числа a і для них перевіряється умова (2). Якщо знаходиться свідок непростота, то доведено, що число P - Складене. В іншому випадку говорять, що P - Просте з деякою ймовірністю.


4. Застосування

Головним чином, символ Якобі використовується для швидкого обчислення символу Лежандра.

Символ Лежандра, в свою чергу, необхідний для перевірки можливості розв'язання квадратичного порівняння по модулю простого числа. Але вважати його за визначенням (тобто обчислювати a ^ {\ frac {p-1} {2}} \ mod {p} ) - Досить довга за часом процедура. За допомогою алгоритму швидкого зведення в ступінь це робиться за O (\ log ^ 3 p) бітових операцій (якщо не використовувати швидке множення і ділення). А обчислення символу Якобі вимагає тільки O (\ log ^ 2 p) бітових операцій.

Символ Якобі використовується в деяких тестах на простоту, наприклад, в (N +1)-методах і, як уже було сказано, в тесті Соловея - штрассе.


5. Алгоритм

5.1. Основна ідея

Ключове використовуване при обчисленні властивість символу Якобі - квадратичний закон взаємності. Завдяки ньому алгоритм схожий на алгоритм Евкліда знаходження найбільшого спільного дільника двох чисел, в якому теж аргументи на кожному кроці міняються місцями. Аналогічно алгоритмом Евкліда, при перестановці аргументів більший замінюється на залишок від ділення на менший. Це можливо завдяки періодичності символу Якобі. Однак, оскільки символ Якобі визначений тільки за умови непарності другого аргументу, то до перестановки виділяється парна частина першого аргументу.


5.2. Формальне опис

Вхідні дані: a - ціле число, b - натуральне, непарне, більше одиниці.

Вихідні дані: \ Left (\ frac {a} {b} \ right) - Символ Якобі


 1 (перевірка взаємної простоти). Якщо НСД (a, b) ≠ 1, вихід з алгоритму з відповіддю 0. 2 (ініціалізація). R: = 1 3 (перехід до позитивних числах). Якщо a <0 то a: =-a Якщо b mod 4 = 3 то r: =-r Кінець якщо 4 (позбавлення від парності). t: = 0 Цикл ПОКИ a - парне t: = t +1 a: = a / 2 Кінець циклу Якщо t - непарне, то Якщо b mod 8 = 3 або 5, то r: = - r. Кінець якщо 5 (квадратичний закон взаємності). Якщо a mod 4 = b mod 4 = 3, то r: = - r. c: = a; a: = b mod c; b: = c. 6 (вихід з алгоритму?). Якщо a ≠ 0, то йти на крок 4, інакше вийти з алгоритму з відповіддю r. 

5.3. Коментарі до алгоритму

В алгоритмі скрізь береться найменший позитивний вирахування (тобто залишок від ділення).

На четвертому кроці використовується мультипликативность символу Якобі, а потім обчислюється символ Якобі \ Left (\ frac {2} {b} \ right) = (-1) ^ {(b ^ 2-1) / 8} . Щоб уникнути зайвого зведення в ступінь, перевіряється тільки залишок від ділення b на 8.

На п'ятому кроці теж замість зведення в ступінь використовується перевірка залишків від ділення.

Складність алгоритму дорівнює O (\ log {a} \ cdot \ log {b}) бітових операцій.


6. Приклад обчислення

Обчислення символу Лежандра за допомогою символу Якобі:

7. Список літератури

  • Василенко О.М. Теоретико-числові алгоритми в криптографії. - Москва: МЦМНО, 2003. - С. 328. - ISBN 5-94057-103-4 .
  • Виноградов І. М. Основи теорії чисел. - Москва: ГІТТЛ, 1952.
  • Bach E., Shallit J. Algorithmic Number Theory. Vol. I. - Massachusetts: MIT Press, 1996. - ISBN 0-262-02405-5 .
Перегляд цього шаблону Характери в теорії чисел і Характер в теорії груп
Квадратичні характери Символ Лежандра Символ Якобі Символ Кронекера - Якобі
Характери статечних відрахувань Характер кубічного вирахування Характер біквадратичних відрахування Символ статечного вирахування