Symbol Jacobiego

Symbol Jacobiego – uogólnienie symbolu Legendre’a na liczby nieparzyste niekoniecznie pierwsze: jeśli rozkład $n$ na czynniki pierwsze to $p_{1}^{c_{1}}p_{2}^{c_{2}}\cdots p_{k}^{c_{k}},$ to symbol Jacobiego jest równy przez symbol Legendre’a:

$\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{c_{1}}\left({\frac {a}{p_{2}}}\right)^{c_{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{c_{k}}$

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

Własności:

Jeśli $a=b\mod n,$ to $\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)$

$\left({\frac {a}{n}}\right)=0$ wtedy i tylko wtedy, gdy $a$ i $n$ nie są względnie pierwsze

$\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)$

$\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)$

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

$\left({\frac {-1}{n}}\right)=1$ jeśli $n=1\mod 4$

$\left({\frac {-1}{n}}\right)=-1$ jeśli $n=3\mod 4$

$\left({\frac {2}{n}}\right)=1$ jeśli $n=1\mod 8$ lub $n=7\mod 8$

$\left({\frac {2}{n}}\right)=-1$ jeśli $n=3\mod 8$ lub $n=5\mod 8$

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

$\left({\frac {m}{n}}\right)=\left({\frac {n}{m}}\right)(-1)^{\frac {(m-1)(n-1)}{4}}$

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

$\left({\frac {2^{x}y}{n}}\right)=\left({\frac {2^{x}}{n}}\right)\left({\frac {y}{n}}\right)=\left({\frac {2}{n}}\right)^{x}\left({\frac {n}{y}}\right)(-1)^{(n-1)(y-1)/4}=\left({\frac {2}{n}}\right)^{x}\left({\frac {n{\bmod {y}}}{y}}\right)(-1)^{(n-1)(y-1)/4}=\left({\frac {n{\bmod {y}}}{y}}\right)(-1)^{(n-1)(x(n+1)+2(y-1))/8}$

Na podstawie tego wzoru można zbudować rekurencyjny algorytm (wszystkie dzielenia i reszty modulo z wyjątkiem $n{\bmod {y}}$ 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

• Obliczanie symbolu Jacobiego. math.fau.edu. [zarchiwizowane z tego adresu (2008-07-20)].
• Eric W.E.W. Weisstein Eric W.E.W., Jacobi Symbol, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
• Jacobi symbol (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].