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=bmodn,$ 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=1mod4$

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

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

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

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{nmody}{y}\right)(-1{)}^{(n-1)(y-1)/4}=\left(\frac{nmody}{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 $nmody$ 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

• Szablon:Cytuj stronę
• Szablon:MathWorld
• Szablon:Otwarty dostęp Jacobi symbol Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].