Введение
Обобщение символа Лежандра в теории чисел
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 3 0 1 −1 5 0 1 −1 −1 1 7 0 1 1 −1 1 −1 −1 9 0 1 1 0 1 1 0 1 1 11 0 1 −1 1 1 1 −1 −1 −1 1 −1 13 0 1 −1 1 1 −1 −1 −1 −1 1 1 −1 1 15 0 1 1 0 1 0 0 −1 1 0 0 −1 0 −1 −1 17 0 1 1 −1 1 −1 −1 −1 1 1 −1 −1 −1 1 −1 1 1
Символ Якоби для различных k (вверху) и n (слева). Показаны только значения 0 ≤ k < n, поскольку согласно правилу (2) ниже любое другое значение k можно привести по модулю n. Квадратичные остатки выделены жёлтым цветом — обратите внимание, что ни одно значение с символом Якоби −1 не является квадратичным остатком, и если k является квадратичным остатком по модулю взаимно простого n, то , но не все значения с символом Якоби 1 (см. строки 1=n = 9 и 1=n = 15) являются квадратичными остатками. Также заметьте, что когда n или k является полным квадратом, все значения неотрицательны. Символ Якоби является обобщением символа Лежандра. Введённый Якоби в 1837 году, он представляет теоретический интерес в модульной арифметике и других областях теории чисел, но его основное применение — в вычислительной теории чисел, особенно в проверке простоты и факторизации целых чисел; эти, в свою очередь, важны в криптографии.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 3 0 1 −1 5 0 1 −1 −1 1 7 0 1 1 −1 1 −1 −1 9 0 1 1 0 1 1 0 1 1 11 0 1 −1 1 1 1 −1 −1 −1 1 −1 13 0 1 −1 1 1 −1 −1 −1 −1 1 1 −1 1 15 0 1 1 0 1 0 0 −1 1 0 0 −1 0 −1 −1 17 0 1 1 −1 1 −1 −1 −1 1 1 −1 −1 −1 1 −1 1 1
Jacobi symbol for various k (along top) and n (along left side). Only 0 ≤ k < n are shown, since due to rule (2) below any other k can be reduced modulo n. Quadratic residues are highlighted in yellow — note that no entry with a Jacobi symbol of −1 is a quadratic residue, and if k is a quadratic residue modulo a coprime n, then , but not all entries with a Jacobi symbol of 1 (see the 1=n = 9 and 1=n = 15 rows) are quadratic residues. Notice also that when either n or k is a square, all values are nonnegative. The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.
Расчет символа Якоби
Вышеуказанные формулы приводят к эффективному алгоритму в нотации «Большое О» для вычисления символа Якоби, аналогичному алгоритму Евклида для нахождения НОД двух чисел. (Это не должно удивлять, учитывая правило 2.) Уменьшите «числитель» по модулю «знаменателя», используя правило 2. Извлеките любой четный «числитель», используя правило 9. Если «числитель» равен 1, правила 3 и 4 дают результат 1. Если «числитель» и «знаменатель» не взаимно просты, правило 3 дает результат 0. В противном случае, «числитель» и «знаменатель» теперь являются нечетными положительными взаимно простыми целыми числами, поэтому мы можем инвертировать символ, используя правило 6, а затем вернуться к шагу 1. Помимо кода, представленного ниже, Ризель реализовал его на Паскале.
Пример расчетов
Символ Лежендра определен только для нечетных простых чисел p. Он подчиняется тем же правилам, что и символ Якоби (то есть, закону взаимности и дополнительным формулам для (0/p) и (2/p), а также мультипликативности "числителя"). Задача: зная, что 9907 является простым числом, вычислите (3/9907).
Используя символ Якоби
Разница между двумя вычислениями заключается в том, что при использовании символа Лежандра "числитель" необходимо разложить на простые множители в степенях перед инвертированием символа. Это делает вычисление с использованием символа Лежандра значительно медленнее, чем вычисление с использованием символа Якоби, поскольку не существует известного алгоритма полиномиального времени для факторизации целых чисел. Фактически, именно поэтому Якоби и ввел этот символ.
Испытание первичности
Есть еще один способ, которым символы Якоби и Лежандра различаются. Если формула критерия Эйлера используется по модулю составного числа, результат может совпадать, а может и не совпадать со значением символа Якоби, и вообще может не равняться ни −1, ни 1. Например,
если неизвестно, является ли число n простым или составным, можно выбрать случайное число a, вычислить символ Якоби и сравнить его с формулой Эйлера; если они отличаются по модулю n, то n составное; если они дают один и тот же остаток по модулю n для многих различных значений a, то n "вероятно простое". Это лежит в основе вероятностного теста простоты Соловая — Штрассена и его усовершенствований, таких как тест простоты Бейли — PSW и тест простоты Миллера — Рабина. В качестве косвенного применения его можно использовать как процедуру обнаружения ошибок при выполнении теста простоты Лукаса — Лемера, который даже на современном компьютерном оборудовании может занимать недели для завершения обработки чисел Мерсенна (наибольшее известное число Мерсенна, являющееся простым, по состоянию на декабрь 2018 года). В нормальных случаях символ Якоби:
Это также справедливо для конечного остатка и, следовательно, может использоваться для проверки вероятной корректности. Однако, если в аппаратном обеспечении произойдет ошибка, существует вероятность 50%, что результат станет 0 или 1 вместо этого и не изменится при последующих итерациях (если только другая ошибка не вернет его к 1).