символ Якоби

Обобщение символа Лежандра в теории чисел

Карл Густав Якоб Якоби, который ввел этот символ.

Символ Якоби ( ⁠к/н⁠ ) ​​для различных k (вверху) и n (вдоль левой стороны). Показаны только 0 ≤ k < n , поскольку из-за правила (2) ниже любое другое k может быть сокращено по модулю n . Квадратичные вычеты выделены желтым цветом — обратите внимание, что ни одна запись с символом Якоби −1 не является квадратичным вычетом, а если k является квадратичным вычетом по модулю взаимно простого числа n , то ( ⁠к/н⁠ ) ​​= 1 , но не все записи с символом Якоби 1 (см. строки n = 9 и n = 15 ) являются квадратичными остатками. Обратите также внимание, что когда n или k являются квадратами, все значения неотрицательны.

Символ Якоби является обобщением символа Лежандра . Введенный Якоби в 1837 году, ^[1] он представляет теоретический интерес для модульной арифметики и других разделов теории чисел , но его основное применение — в вычислительной теории чисел , особенно в проверке простоты и факторизации целых чисел ; они, в свою очередь, важны в криптографии .

Определение

Для любого целого числа a и любого положительного нечетного целого числа n символ Якоби ( ⁠а/н⁠ ) ​​определяется как произведение символов Лежандра, соответствующих простым множителям n :

${\displaystyle \left({\frac {a}{n}}\right):=\left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\left({\frac {a}{p_{2}}}\right)^{\alpha _{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{\alpha _{k}},}$

где

${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}$

является разложением на простые множители числа n .

Символ Лежандра ( ⁠а/п⁠ ) ​​определяется для всех целых чисел a и всех нечетных простых чисел p формулой

${\displaystyle \left({\frac {a}{p}}\right):=\left\{{\begin{array}{rl}0&{\text{if }}a\equiv 0{\pmod {p}},\\1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x\colon \;a\equiv x^{2}{\pmod {p}},\\-1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and there is no such }}x.\end{array}}\right.}$

Следуя обычному соглашению для пустого продукта, ( ⁠а/1⁠ ) ​​= 1.

Когда нижний аргумент является нечетным простым числом, символ Якоби равен символу Лежандра.

Таблица значений

Ниже приведена таблица значений символа Якоби ( ⁠к/н⁠ ) ​​при n  ≤ 59, k  ≤ 30, n нечетное.

Характеристики

Следующие факты, даже законы взаимности, являются прямыми выводами из определения символа Якоби и соответствующих свойств символа Лежандра. ^[2]

Символ Якоби определен только тогда, когда верхний аргумент («числитель») является целым числом, а нижний аргумент («знаменатель») — положительным нечетным целым числом.

1. Если n — (нечетное) простое число, то символ Якоби ( ⁠а/н⁠ ) ​​равен (и записывается так же) соответствующему символу Лежандра.

2. Если a ≡ b  (mod n ) , то ${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)=\left({\frac {a\pm m\cdot n}{n}}\right)}$

3. ${\displaystyle \left({\frac {a}{n}}\right)={\begin{cases}0&{\text{if }}\gcd(a,n)\neq 1,\\\pm 1&{\text{if }}\gcd(a,n)=1.\end{cases}}}$

Если фиксирован верхний или нижний аргумент, то символ Якоби является полностью мультипликативной функцией по оставшемуся аргументу:

4. ${\displaystyle \left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right),\quad {\text{so }}\left({\frac {a^{2}}{n}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.}$

5. ${\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right),\quad {\text{so }}\left({\frac {a}{n^{2}}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.}$

Закон квадратичной взаимности : если m и n — нечетные положительные взаимно простые целые числа, то

6. ${\displaystyle \left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{{\tfrac {m-1}{2}}\cdot {\tfrac {n-1}{2}}}={\begin{cases}1&{\text{if }}n\equiv 1{\pmod {4}}{\text{ or }}m\equiv 1{\pmod {4}},\\-1&{\text{if }}n\equiv m\equiv 3{\pmod {4}}\end{cases}}}$

и его добавки

7. , ${\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\tfrac {n-1}{2}}={\begin{cases}1&{\text{if }}n\equiv 1{\pmod {4}},\\-1&{\text{if }}n\equiv 3{\pmod {4}},\end{cases}}}$

и ${\displaystyle \left({\frac {1}{n}}\right)=\left({\frac {n}{1}}\right)=1}$

8. ${\displaystyle \left({\frac {2}{n}}\right)=(-1)^{\tfrac {n^{2}-1}{8}}={\begin{cases}1&{\text{if }}n\equiv 1,7{\pmod {8}},\\-1&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}}$

Объединение свойств 4 и 8 дает:

9. ${\displaystyle \left({\frac {2a}{n}}\right)=\left({\frac {2}{n}}\right)\left({\frac {a}{n}}\right)={\begin{cases}\left({\frac {a}{n}}\right)&{\text{if }}n\equiv 1,7{\pmod {8}},\\{-\left({\frac {a}{n}}\right)}&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}}$

Как символ Лежандра:

• Если ( ⁠а/н⁠ )  ​​= −1, то a является квадратичным невычетом по модулю n .

• Если a — квадратичный вычет по модулю n и gcd ( a , n ) = 1, то ( ⁠а/н⁠ )  ​​= 1.

Но, в отличие от символа Лежандра:

Если ( ⁠а/н⁠ )  ​​= 1, то a может быть, а может и не быть квадратичным вычетом по модулю n .

Это потому, что для того, чтобы a был квадратичным вычетом по модулю n , он должен быть квадратичным вычетом по модулю каждого простого множителя n . Однако символ Якоби равен единице, если, например, a является невычетом по модулю ровно двух простых множителей n .

Хотя символ Якоби нельзя единообразно интерпретировать в терминах квадратов и неквадратов, его можно единообразно интерпретировать как знак перестановки по лемме Золотарева .

Символ Якоби ( ⁠а/н⁠ ) ​​является характером Дирихле по модулю n .

Вычисление символа Якоби

Приведенные выше формулы приводят к эффективному алгоритму O (log a log b ) ^[3] для вычисления символа Якоби, аналогичному алгоритму Евклида для нахождения наибольшего общего делителя двух чисел. (Это не должно удивлять в свете правила 2.)

1. Уменьшите «числитель» по модулю «знаменателя», используя правило 2.
2. Извлеките любой четный «числитель», используя правило 9.
3. Если «числитель» равен 1, правила 3 ​​и 4 дают результат 1. Если «числитель» и «знаменатель» не являются взаимно простыми, правило 3 дает результат 0.
4. В противном случае «числитель» и «знаменатель» теперь являются нечетными положительными взаимно простыми целыми числами, поэтому мы можем перевернуть символ, используя правило 6, а затем вернуться к шагу 1.

В дополнение к приведенному ниже коду, Riesel ^[4] имеет его на языке Pascal.

Реализация вЛуа

функция  jacobi ( n ,  k )  assert ( k  >  0  и  k  %  2  ==  1 )  n  =  n  %  k  t  =  1  while  n  ~=  0  do  while  n  %  2  ==  0  do  n  =  n  /  2  r  =  k  %  8  if  r  ==  3  or  r  ==  5  then  t  =  - t  end  end  n ,  k  =  k ,  n  if  n  %  4  ==  3  and  k  %  4  ==  3  then  t  =  - t  end  n  =  n  %  k  end  if  k  ==  1  then  return  t  else  return  0  end end

Реализация вС++

// a/n представлено как (a,n) int jacobi ( int a , int n ) { assert ( n > 0 && n % 2 == 1 ); // шаг 1 a = ( a % n + n ) % n ; // Обработка (a < 0) int t = 1 ; int r ; // шаг 3 while ( a != 0 ) { // шаг 2 while ( a % 2 == 0 ) { a /= 2 ; r = n % 8 ; if ( r == 3 || r == 5 ) { t = - t ; } } // шаг 4 r = n ; n = a ; a = r ; if ( a % 4 == 3 && n % 4 == 3 ) { t = - t ; } a = a % n ; } if ( n == 1 ) { return t ; } иначе { вернуть 0 ; } }                                                                                                               

Пример расчета

Символ Лежандра ( ⁠а/п⁠ ) ​​определен только для нечетных простых чисел p . Он подчиняется тем же правилам, что и символ Якоби (т. е. взаимности и дополнительным формулам для ( ⁠−1/п⁠ ) ​​и ( ⁠2/п⁠ ) ​​и мультипликативность «числителя».)

Задача: учитывая, что 9907 — простое число, вычислить ( ⁠1001/9907⁠ ) ​​.

Использование символа Лежандра

${\displaystyle {\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {7}{9907}}\right)\left({\frac {11}{9907}}\right)\left({\frac {13}{9907}}\right).\\\left({\frac {7}{9907}}\right)&=-\left({\frac {9907}{7}}\right)=-\left({\frac {2}{7}}\right)=-1.\\\left({\frac {11}{9907}}\right)&=-\left({\frac {9907}{11}}\right)=-\left({\frac {7}{11}}\right)=\left({\frac {11}{7}}\right)=\left({\frac {4}{7}}\right)=1.\\\left({\frac {13}{9907}}\right)&=\left({\frac {9907}{13}}\right)=\left({\frac {1}{13}}\right)=1.\\\left({\frac {1001}{9907}}\right)&=-1.\end{aligned}}}$

Использование символа Якоби

${\displaystyle {\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {9907}{1001}}\right)=\left({\frac {898}{1001}}\right)=\left({\frac {2}{1001}}\right)\left({\frac {449}{1001}}\right)=\left({\frac {449}{1001}}\right)\\&=\left({\frac {1001}{449}}\right)=\left({\frac {103}{449}}\right)=\left({\frac {449}{103}}\right)=\left({\frac {37}{103}}\right)=\left({\frac {103}{37}}\right)\\&=\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {2}{29}}\right)^{3}=-1.\end{aligned}}}$

Разница между двумя вычислениями заключается в том, что при использовании символа Лежандра «числитель» должен быть разложен на простые множители, прежде чем символ будет перевернут. Это делает вычисления с использованием символа Лежандра значительно медленнее, чем с использованием символа Якоби, поскольку не существует известного алгоритма полиномиального времени для факторизации целых чисел. ^[5] Фактически, именно поэтому Якоби ввел этот символ.

Тестирование простоты

Есть еще один способ, которым символы Якоби и Лежандра различаются. Если формула критерия Эйлера используется по модулю составного числа, результат может быть или не быть значением символа Якоби, и на самом деле может даже не быть −1 или 1. Например,

${\displaystyle {\begin{aligned}\left({\frac {19}{45}}\right)&=1&&{\text{ and }}&19^{\frac {45-1}{2}}&\equiv 1{\pmod {45}}.\\\left({\frac {8}{21}}\right)&=-1&&{\text{ but }}&8^{\frac {21-1}{2}}&\equiv 1{\pmod {21}}.\\\left({\frac {5}{21}}\right)&=1&&{\text{ but }}&5^{\frac {21-1}{2}}&\equiv 16{\pmod {21}}.\end{aligned}}}$

Таким образом, если неизвестно, является ли число n простым или составным, мы можем выбрать случайное число a , вычислить символ Якоби ( ⁠а/н⁠ ) ​​и сравните ее с формулой Эйлера; если они различаются по модулю n , то n является составным; если они имеют одинаковый остаток по модулю n для многих различных значений a , то n является « вероятно простым ».

Это основа вероятностного теста простоты Соловея-Штрассена и его усовершенствований, таких как тест простоты Бейли-ПСВ и тест простоты Миллера-Рабина .

В качестве косвенного использования его можно использовать в качестве процедуры обнаружения ошибок во время выполнения теста простоты Люка-Лемера , который даже на современном компьютерном оборудовании может занять недели при обработке чисел Мерсенна более (наибольшее известное простое число Мерсенна по состоянию на октябрь 2024 года). В номинальных случаях символ Якоби: ${\displaystyle {\begin{aligned}2^{136,279,841}-1\end{aligned}}}$

${\displaystyle {\begin{aligned}\left({\frac {s_{i}-2}{M_{p}}}\right)&=-1&i\neq 0\end{aligned}}}$

Это также справедливо для конечного остатка и, следовательно, может использоваться в качестве проверки вероятной валидности. Однако, если в оборудовании возникает ошибка, существует 50% вероятность того, что результат станет 0 или 1 вместо этого и не изменится с последующими членами (если только не произойдет другая ошибка и не изменит его обратно на -1). ${\displaystyle {\begin{aligned}s_{p-2}\end{aligned}}}$ ${\displaystyle {\begin{aligned}s\end{aligned}}}$

Смотрите также

• Символ Кронекера — обобщение символа Якоби на все целые числа.
• Символ степенного вычета , обобщение символа Якоби на вычеты более высоких степеней.

Примечания

1. Якоби, CGJ (1837). «Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie». Берихт Ак. Висс. Берлин : 127–136.
2. Айрленд и Розен, стр. 56–57 или Леммермейер, стр. 10
3. Коэн, стр. 29–31.
4. стр. 285
5. Решето числового поля , самый быстрый из известных алгоритмов, требует

   ${\displaystyle O\left(e^{(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}{\big (}C+o(1){\big )}}\right)}$

   операции по факторизации n . См. Коэн, стр. 495

Ссылки

• Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел . Берлин: Springer . ISBN 3-540-55640-0.
• Айрленд, Кеннет; Розен, Майкл (1990). Классическое введение в современную теорию чисел (второе изд.). Нью-Йорк: Springer . ISBN 0-387-97329-X.
• Леммермейер, Франц (2000). Законы взаимности: от Эйлера до Эйзенштейна . Берлин: Шпрингер . ISBN 3-540-66957-4.
• Ризель, Ганс (1994), Простые числа и компьютерные методы факторизации (второе издание) , Бостон: Birkhäuser, ISBN 0-8176-3743-5
• Шаллит, Джеффри (декабрь 1990 г.). «О худшем случае трех алгоритмов вычисления символа Якоби». Журнал символических вычислений . 10 (6): 593–61. doi : 10.1016/S0747-7171(08)80160-5 . Технический отчет по информатике PCS-TR89-140.
• Валле, Брижит ; Леме, Чарли (октябрь 1998 г.). Анализ среднего случая трех алгоритмов вычисления символа Якоби (технический отчет). CiteSeerX  10.1.1.32.3425 .
• Эйкенберри, Шона Мейер; Соренсон, Джонатан П. (октябрь 1998 г.). "Эффективные алгоритмы вычисления символа Якоби" (PDF) . Журнал символических вычислений . 26 (4): 509–523. CiteSeerX  10.1.1.44.2423 . doi :10.1006/jsco.1998.0226.

Внешние ссылки

• Рассчитайте символ Якоби. Архивировано 05.10.2016 на Wayback Machine. Показаны этапы расчета.