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
Jacobi symbol , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].
Kategoria:Teoria liczb Kategoria:Arytmetyka modularna