Przejdź do zawartości

Symbol Jacobiego

Z Wikipedii, wolnej encyklopedii

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

[edytuj | edytuj kod]