Символ Якоби

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

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

Определение [ править ]

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

\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}},

где

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

является простой факторизацией n .

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

\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.

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

Таблица значений [ править ]

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

к н	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
1	− 1	1	1	− 1	1	1	1	1	− 1	1	1	1	1	1	1	− 1	1	1	1	1	1	1	1	1	− 1	1	1	1	1	1
3	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
5	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0
7	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1
9	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0
11	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1
13	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1
15	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0
17	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	1	0	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1
19	1	−1	−1	1	1	1	1	−1	1	−1	1	−1	−1	−1	−1	1	1	−1	0	1	−1	−1	1	1	1	1	−1	1	−1	1
21	1	−1	0	1	1	0	0	−1	0	−1	−1	0	−1	0	0	1	1	0	−1	1	0	1	−1	0	1	1	0	0	−1	0
23	1	1	1	1	−1	1	−1	1	1	−1	−1	1	1	−1	−1	1	−1	1	−1	−1	−1	−1	0	1	1	1	1	−1	1	−1
25	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0
27	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
29	1	−1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	1	1	−1	−1	1	0	1
31	1	1	−1	1	1	−1	1	1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	1	−1	−1	1	−1	−1
33	1	1	0	1	−1	0	−1	1	0	−1	0	0	−1	−1	0	1	1	0	−1	−1	0	0	−1	0	1	−1	0	−1	1	0
35	1	−1	1	1	0	−1	0	−1	1	0	1	1	1	0	0	1	1	−1	−1	0	0	−1	−1	−1	0	−1	1	0	1	0
37	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	−1	−1	1	1	1	1	−1	1
39	1	1	0	1	1	0	−1	1	0	1	1	0	0	−1	0	1	−1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0
41	1	1	−1	1	1	−1	−1	1	1	1	−1	−1	−1	−1	−1	1	−1	1	−1	1	1	−1	1	−1	1	−1	−1	−1	−1	−1
43	1	−1	−1	1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1
45	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0
47	1	1	1	1	−1	1	1	1	1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	1	−1	−1	1	1	−1	1	1	−1	−1
49	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1
51	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	1	0	1	0	0	1	1	0	−1	1	0	1	−1	0	−1	1	0
53	1	−1	−1	1	−1	1	1	−1	1	1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1	−1	1	1	−1	−1	1	1	−1
55	1	1	−1	1	0	−1	1	1	1	0	0	−1	1	1	0	1	1	1	−1	0	−1	0	−1	−1	0	1	−1	1	−1	0
57	1	1	0	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	−1	0	0	−1	0	−1	−1	0	1	−1	0	1	1	0
59	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	−1	−1	1	1	1	1	1	−1

Свойства [ править ]

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

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

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

2. Если a ≡ b (mod n ) , то

\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)=\left({\frac {a\pm m\cdot n}{n}}\right)

3.

\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.

\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.

\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.

\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.

\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}}

,

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

8.

\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.

\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}}

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

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

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

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

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

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

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

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

Вычисление символа Якоби [ править ]

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

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

В дополнение к приведенному ниже коду Ризель ^[4] есть это в Паскале.

Реализация на Lua [ править ]

function jacobi(n, k)
  assert(k > 0 and 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

Реализация на C++ [ править ]

// a/n is represented as (a,n)
int jacobi(int a, int n) {
    assert(n > 0 && n%2 == 1);
    //step 1
    a = a % n;
    int t = 1;
    int r;
    //step 3
    while (a != 0) {
        //step 2
        while (a % 2 == 0) {
            a /= 2;
            r = n % 8;
            if (r == 3 || r == 5) {
                t = -t;
            }
        }
        //step 4
        r = n;
        n = a;
        a = r;
        if (a % 4 == 3 && n % 4 == 3) {
            t = -t;
        }
        a = a % n;
    }
    if (n == 1) {
        return t;
    }
    else {
        return 0;
    }
}

Пример расчетов [ править ]

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

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

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

{\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}}

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

{\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. Например,

{\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 « вероятно простое число ».

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

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

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

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

См. также [ править ]

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

Примечания [ править ]

^ Якоби, CGJ (1837). «О делении кругов и его приложении к теории чисел». Сообщить Ак. Знать. Берлин : 127–136.
^ Ирландия и Розен, стр. 56–57 или Леммермейер, стр. 56–57. 10
^ Коэн, стр. 29–31.
^ с. 285
^ Решето числового поля , самый быстрый из известных алгоритмов, требует
$O\left(e^{(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}{\big (}C+o(1){\big )}}\right)$
операции по фактору n . См. Коэн, с. 495

Ссылки [ править ]

Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел . Берлин: Шпрингер . ISBN 3-540-55640-0 .
Ирландия, Кеннет; Розен, Майкл (1990). Классическое введение в современную теорию чисел (второе изд.). Нью-Йорк: Спрингер . ISBN 0-387-97329-Х .
Леммермейер, Франц (2000). Законы взаимности: от Эйлера до Эйзенштейна . Берлин: Шпрингер . ISBN 3-540-66957-4 .
Ризель, Ганс (1994), Простые числа и компьютерные методы факторизации (второе издание) , Бостон: Birkhäuser, ISBN 0-8176-3743-5
Шалит, Джеффри (декабрь 1990 г.). «О наихудшем случае трех алгоритмов вычисления символа Якоби» . Журнал символических вычислений . 10 (6): 593–61. дои : 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 . дои : 10.1006/jsco.1998.0226 .

Внешние ссылки [ править ]

Символ «Рассчитать Якоби» показывает этапы расчета.

[1] Якоби, CGJ (1837). «О делении кругов и его приложении к теории чисел». Сообщить Ак. Знать. Берлин : 127–136.

[2] Ирландия и Розен, стр. 56–57 или Леммермейер, стр. 56–57. 10

[3] Коэн, стр. 29–31.

[4] с. 285

[5] Решето числового поля , самый быстрый из известных алгоритмов, требует
$O\left(e^{(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}{\big (}C+o(1){\big )}}\right)$
операции по фактору n . См. Коэн, с. 495

[1]

[2]

[3]

[4]

[5]