Symbol Jacobiego

Symbol Jacobiego – uogólnienie symbolu Legendre'a na liczby nieparzyste niekoniecznie pierwsze: jeśli rozkład na czynniki pierwsze to , to symbol Jacobiego jest równy przez symbol Legendre'a:

Można zauważyć, że jeśli jest pierwsze, symbol Jacobiego jest równy symbolowi Legendre'a.

Własności:

Jeśli , to
wtedy i tylko wtedy, gdy i nie są względnie pierwsze
jeśli
jeśli
jeśli lub
jeśli lub

Zachodzi też odpowiednio uogólnione prawo wzajemności reszt kwadratowych:

Choć w definicji symbolu Jacobiego występuje faktoryzacja, istnieje jednak szybki algorytm obliczania go bez użycia faktoryzacji. Zauważmy, że ( nieparzyste):

Na podstawie tego wzoru można zbudować rekurencyjny algorytm (wszystkie dzielenia i reszty modulo z wyjątkiem to w rzeczywistości proste operacje bitowe):

Symbol-Jacobiego(a,n)
  if even(n)
    throw Błąd
  if a == 0
    return 0
  if a == 1
    return 1
  x = 0
  y = a
  while even(y)
    y = y / 2
    x = x + 1
  if odd(x) and (n mod 8 == 3 or n mod 8 == 5)
    wynik = -1
  else
    wynik = 1
  if n mod 4 == 3 and y mod 4 == 3
    wynik = -wynik
  if y == 1
    return wynik
  else
    return wynik * Symbol-Jacobiego(n mod y, y)
  • linki zewnętrzne

Linki zewnętrzne

Inne języki
čeština: Jacobiho symbol
Deutsch: Jacobi-Symbol
English: Jacobi symbol
Esperanto: Jakobia simbolo
한국어: 야코비 기호
Nederlands: Jacobi-symbool
ភាសាខ្មែរ: សញ្ញាយ៉ាកូប៊ី
português: Símbolo de Jacobi
русский: Символ Якоби
Türkçe: Jacobi sembolü
українська: Символ Якобі
Tiếng Việt: Kí hiệu Jacobi