Symbol Jacobiego

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

${\displaystyle \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 ${\displaystyle n}$ jest pierwsze, symbol Jacobiego jest równy symbolowi Legendre’a.

Własności:

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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 (${\displaystyle y}$ nieparzyste):

${\displaystyle \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 ${\displaystyle 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].