Symbol Jacobiego

Z Wikipedii

Symbol Jacobiego to 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

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 odwrotnoś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^xy} 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}$

Na podstawie tego wzoru można zbudować rekurencyjny algorytm (wszystkie dzielenia i reszty modulo z wyjątkiem $n mod 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 even(x) and (n mod 8 == 3 or n mod 8 == 5)
    wynik = 1
  else
    wynik = -1
  if n mod 4 == 3 and a mod 4 == 3
    wynik = -wynik
  if y == 1
    return wynik
  else
    return wynik * Symbol-Jacobiego(n mod y, y)