Jacobijev simbol

Jacobijev simbol je posplošitev Legendrovega simbola. Uvedel ga je Jacobi leta 1837,^[1] navezuje pa se na modularno aritmetiko in ostale veje teorije števil, a glavna uporaba pa se nahaja v računalniški teoriji števil, še posebej v praštevilskem testu in praštevilskem razcepu; te stvari so zelo pomembne v kriptografiji.

k n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	1
3	0	1	−1
5	0	1	−1	−1	1
7	0	1	1	−1	1	−1	−1
9	0	1	1	0	1	1	0	1	1
11	0	1	−1	1	1	1	−1	−1	−1	1	−1
13	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1
15	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1
17	−0	−1	1	−1	−1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	1	1

Jacobijev simbol (⁠k/n⁠) za različne k (proti vrhu) in n (proti levi). Prikazani so samo 0 ≤ k < n, saj se zaradi pravila (2) spodaj da zmanjšati k za modulo n. Kvadratni ostanki so označeni z rumeno — oglej si, da noben vnos z Jacobijevim simbolom −1 ni kvadratni ostanek, če pa je k kvadratni ostanek modula tujega števila n, potem je (⁠k/n⁠) = 1, a niso vsi vnosi Jacobijevega simbola 1 (glej vrsti n = 9 in n = 15) kvadratni ostanki. Opazimo tudi, da če je eden izmed n ali k kvadrat, so vse vrednosti nenegativne.

Definicija

Za katerokoli celo število a in liho naravno število n, je Jacobijev simbol (⁠a/n⁠) definiran kot produkt Legendrovih simbolov, ki predstavljajo praštevilski razcep od n:

\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\left({\frac {a}{p_{2}}}\right)^{\alpha _{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{\alpha _{k}},

kjer je

n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}

praštevilski razcep od n.

Legendrov simbol (⁠a/p⁠) je za vsa cela števila a in vsa liha praštevila p definiran

\left({\frac {a}{p}}\right)=\left\{{\begin{array}{rl}0&{\text{če }}a\equiv 0{\pmod {p}},\\1&{\text{če }}a\not \equiv 0{\pmod {p}}{\text{ in za neko celo število }}x\colon \;a\equiv x^{2}{\pmod {p}},\\-1&{\text{če }}a\not \equiv 0{\pmod {p}}{\text{ in ne obstaja noben tak }}x.\end{array}}\right.

Po standardnem sporazumu za prazni produkt, velja (⁠a/1⁠) = 1.

Ko je nižji argument liho praštevilo, potem je Jacobijev simbol enak Legendrovem simbolu.

Tabela vrednosti

Sledeča tabela je seznam vseh vrednosti Jacobijevega simbola (⁠k/n⁠) za n ≤ 59, k ≤ 30, n je lih.

k n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
1	−1	1	1	−1	1	1	1	1	−1	1	1	1	1	1	1	−1	1	1	1	1	1	1	1	1	−1	1	1	1	1	1
3	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
5	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0
7	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1
9	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0
11	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1
13	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1
15	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0
17	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	1	0	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1
19	1	−1	−1	1	1	1	1	−1	1	−1	1	−1	−1	−1	−1	1	1	−1	0	1	−1	−1	1	1	1	1	−1	1	−1	1
21	1	−1	0	1	1	0	0	−1	0	−1	−1	0	−1	0	0	1	1	0	−1	1	0	1	−1	0	1	1	0	0	−1	0
23	1	1	1	1	−1	1	−1	1	1	−1	−1	1	1	−1	−1	1	−1	1	−1	−1	−1	−1	0	1	1	1	1	−1	1	−1
25	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0
27	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
29	1	−1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	1	1	−1	−1	1	0	1
31	1	1	−1	1	1	−1	1	1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	1	−1	−1	1	−1	−1
33	1	1	0	1	−1	0	−1	1	0	−1	0	0	−1	−1	0	1	1	0	−1	−1	0	0	−1	0	1	−1	0	−1	1	0
35	1	−1	1	1	0	−1	0	−1	1	0	1	1	1	0	0	1	1	−1	−1	0	0	−1	−1	−1	0	−1	1	0	1	0
37	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	−1	−1	1	1	1	1	−1	1
39	1	1	0	1	1	0	−1	1	0	1	1	0	0	−1	0	1	−1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0
41	1	1	−1	1	1	−1	−1	1	1	1	−1	−1	−1	−1	−1	1	−1	1	−1	1	1	−1	1	−1	1	−1	−1	−1	−1	−1
43	1	−1	−1	1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1
45	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0
47	1	1	1	1	−1	1	1	1	1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	1	−1	−1	1	1	−1	1	1	−1	−1
49	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1
51	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	1	0	1	0	0	1	1	0	−1	1	0	1	−1	0	−1	1	0
53	1	−1	−1	1	−1	1	1	−1	1	1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1	−1	1	1	−1	−1	1	1	−1
55	1	1	−1	1	0	−1	1	1	1	0	0	−1	1	1	0	1	1	1	−1	0	−1	0	−1	−1	0	1	−1	1	−1	0
57	1	1	0	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	−1	0	0	−1	0	−1	−1	0	1	−1	0	1	1	0
59	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	−1	−1	1	1	1	1	1	−1

Lastnosti

Sledeča dejstva, celo obratni zakoni, so direktne dedukcije iz definicije Jacobijevega simbola in pripadajočih lastnosti Legendrovega simbola.^[2]

Tacobijev simbol je definiran le, ko je števec celo število in imenovalec pozitivno liho število.

1. Če je n (liho) praštevilo, potem je Jacobijev simbol (⁠an⁠) enak (in zapisan enako kot) pripadajoči Legendrov simbol.

2. Če je a ≡ b (mod n), potem je

\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)=\left({\frac {a\pm m\cdot n}{n}}\right)

3.

\left({\frac {a}{n}}\right)={\begin{cases}0&{\text{če }}D(a,n)\neq 1,\\\pm 1&{\text{če }}D(a,n)=1.\end{cases}}

Če je katerikoli izmed števca ali imenovalca stalen, potem je Jacobijev simbol popolnoma multiplikativna funkcija v preostalem argumentu:

4.

\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right),\quad {\text{torej }}\left({\frac {a^{2}}{n}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ ali }}0.

5.

\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right),\quad {\text{torej }}\left({\frac {a}{n^{2}}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ ali }}0.

Kvadratni recipročnostni zakon: če sta si m in n lihi tuji naravni števili, potem je

6.

\left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{{\tfrac {m-1}{2}}\cdot {\tfrac {n-1}{2}}}={\begin{cases}1&{\text{če }}n\equiv 1{\pmod {4}}{\text{ ali }}m\equiv 1{\pmod {4}},\\-1&{\text{če }}n\equiv m\equiv 3{\pmod {4}}\end{cases}}

7.

\left({\frac {-1}{n}}\right)=(-1)^{\tfrac {n-1}{2}}={\begin{cases}1&{\text{če }}n\equiv 1{\pmod {4}},\\-1&{\text{če }}n\equiv 3{\pmod {4}},\end{cases}}

in to se da prepisati v

8.

\left({\frac {2}{n}}\right)=(-1)^{\tfrac {n^{2}-1}{8}}={\begin{cases}1&{\text{če }}n\equiv 1,7{\pmod {8}},\\-1&{\text{če }}n\equiv 3,5{\pmod {8}}.\end{cases}}

9.

\left({\frac {2a}{n}}\right)=\left({\frac {2}{n}}\right)\left({\frac {a}{n}}\right)={\begin{cases}\left({\frac {a}{n}}\right)&{\text{če }}n\equiv 1,7{\pmod {8}},\\-\left({\frac {a}{n}}\right)&{\text{če }}n\equiv 3,5{\pmod {8}}.\end{cases}}

Če združimo lastnosti 4 in 8 dobimo:

{\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {7}{9907}}\right)\left({\frac {11}{9907}}\right)\left({\frac {13}{9907}}\right).\\\left({\frac {7}{9907}}\right)&=-\left({\frac {9907}{7}}\right)=-\left({\frac {2}{7}}\right)=-1.\\\left({\frac {11}{9907}}\right)&=-\left({\frac {9907}{11}}\right)=-\left({\frac {7}{11}}\right)=\left({\frac {11}{7}}\right)=\left({\frac {4}{7}}\right)=1.\\\left({\frac {13}{9907}}\right)&=\left({\frac {9907}{13}}\right)=\left({\frac {1}{13}}\right)=1.\\\left({\frac {1001}{9907}}\right)&=-1.\end{aligned}}

Kot Legendrov simbol:

Če je (⁠a/n⁠) = −1 potem je a kvadratni modulo n brez ostanka.

Če je a kvadratni ostanek modula n in D(a,n) = 1, potem (⁠a/n⁠) = 1.

A za razliko od Legendrovega simbola:

Če je (⁠an⁠) = 1, potem je a lahko ali pa ne kvadratni modulo n z ostankom.

To se zgodi zato, ker mora za a, ki je kvadratni modulo n z ostankom, obstajati kvadratni modulo z ostankom za vsaki praštevilski faktor od n. A Jacobijev simbol je enak enemu od teh, če je, a enak modulu brez ostanka z natančno dvema izmed praštevilskih faktorjev od n.

Četudi se Jacobijevega simbola ne da unikatno predstaviti s kvadrati in ne-kvadrati, se lahko unikatno opredeli kot znak permutacije po Zolotarevi lemi.

Jacobijev simbol (⁠a/n⁠) je Dirichletov znak k modulom n.

Izračunavanje Jacobijevega simbola

Zgornje formule vodijo v učinkoviti algoritem O(log a log b)^[3] za izračunavanje Jacobijevega simbola, ki je analogen Evklidovemu algoritmu za iskanje največjega skupnega delitelja dveh števil (To se ne zdi preveč presenetljivo zaradi pravila 2).

Zmanjšaj modulo števca na imenovalec z uporabo pravila 2.
Izrazi katerikoli sodi števec z uporabo pravila 9.
Če je števec enak 1, nam dajo pravila 3 in 4 rezultat 1. Če pa števec in imenovalec nista tuji si števili, nam pravilo 3 da rezultat 0.
Če se noben izmed zgornjih primerov ni uresničil, potem sta števec in imenovalec sedaj lihi tuji si naravni števili, kar pomeni, da lahko obrnemo simbol z uporabo pravila 6 in se nato vrnemo na korak 1.

Implementacija v jeziku Lua

function jacobi(n, k)
  assert(k > 0 and k % 2 == 1)
  n = n % k
  t = 1
  while n ~= 0 do
    while n % 2 == 0 do
      n = n / 2
      r = k % 8
      if r == 3 or r == 5 then
        t = -t
      end
    end
    n, k = k, n
    if n % 4 == 3 and k % 4 == 3 then
      t = -t
    end
    n = n % k
  end
  if k == 1 then
    return t
  else
    return 0
  end
end

Primeri računanja

Legendrov simbol (⁠a/p⁠) je definiran le za liha praštevila p. Upošteva enaka pravila kot Jacobijev simbol (torej recipročnost in suplementarne formule za (⁠−1/p⁠) in (⁠2/p⁠) ter multiplikativnost števca.)

Problem: Če je 9907 praštevilo, izračunaj (⁠1001/9907⁠).

Z uporabo Legendrovega simbola

{\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {9907}{1001}}\right)=\left({\frac {898}{1001}}\right)=\left({\frac {2}{1001}}\right)\left({\frac {449}{1001}}\right)=\left({\frac {449}{1001}}\right)\\&=\left({\frac {1001}{449}}\right)=\left({\frac {103}{449}}\right)=\left({\frac {449}{103}}\right)=\left({\frac {37}{103}}\right)=\left({\frac {103}{37}}\right)\\&=\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {2}{29}}\right)^{3}=-1.\end{aligned}}

Z uporabo Jacobijevega simbola

{\begin{aligned}\left({\frac {19}{45}}\right)&=1&&{\text{ in }}&19^{\frac {45-1}{2}}&\equiv 1{\pmod {45}}.\\\left({\frac {8}{21}}\right)&=-1&&{\text{ toda }}&8^{\frac {21-1}{2}}&\equiv 1{\pmod {21}}.\\\left({\frac {5}{21}}\right)&=1&&{\text{ toda }}&5^{\frac {21-1}{2}}&\equiv 16{\pmod {21}}.\end{aligned}}

Razlika med obema izračunoma je v tem, da mora biti Legendrov simbol, ko je uporabljen kot števec, najprej faktoriziran, kasneje šele obrnjen. To spremeni izračun Legendrovega simbola opazno počasnejšega kot Jacobijevega simbola, ker sedaj še ni znan algoritem za polinomsko-časovno faktoriziranje celih števil.^[4] Ravno zato je tudi Jacobi vpeljal svoj simbol.

Praštevilski test

Obstaja še ena stvar, v kateri se oba simbola razlikujeta. Če se za modulo sestavljenega števila uporablja Eulerjeva kriterijska formula, potem je rezultat lahko ali pa ni vrednost Jacobijevega simbola, v resnici lahko celo ni niti −1 niti 1. Na primer

{\begin{aligned}\left({\frac {19}{45}}\right)&=1&&{\text{ in }}&19^{\frac {45-1}{2}}&\equiv 1{\pmod {45}}.\\\left({\frac {8}{21}}\right)&=-1&&{\text{ toda }}&8^{\frac {21-1}{2}}&\equiv 1{\pmod {21}}.\\\left({\frac {5}{21}}\right)&=1&&{\text{ toda }}&5^{\frac {21-1}{2}}&\equiv 16{\pmod {21}}.\end{aligned}}

Torej če je znano, ali je število n praštevilo ali sestavljeno število, lahko izberemo naključno število a, izračunamo Jacobijev simbol (⁠a/n⁠) in ga primerjamo z Eulerjevo formulo; če se razlikuje v modulu n, potem je n sestavljeno število; če pa ima enak ostanek v modulu n za več različnih vrednosti a, potem pa je n "verjetno praštevilo".

To je osnova verjetnostnega Solovay–Strassen praštevilskega testa in zožitve, kot so Baillie-PSW praštevilski test in Miller–Rabin praštevilski test.

Kot posredna uporaba, je to možno uporabiti tudi kot zaznavo napake med izvajanjem Lucas-Lehmer praštevilskega testa, ki se tudi na sodobnih računalnikih lahko izvaja tudi več tednov za izračunavanje Mersennovih števil, ki so višja od ${\begin{aligned}2^{82,589,933}-1\end{aligned}}$ (največje znano Mersennovo število (decembra 2018). V posebnem primeru, je Jacobijev simbol:

${\begin{aligned}\left({\frac {s_{i}-2}{M_{p}}}\right)&=-1&i\neq 0\end{aligned}}$

To drži tudi za končni ostanek ${\begin{aligned}s_{p-2}\end{aligned}}$ in se torej lahko uporablja kot potrditev verjetne veljavnosti. A če se na trdih komponentah računalnika zgodi napaka, potem obstaja 50% možnost, da bo rezultat postal 0 ali 1, in se ne bo spreminjal s ${\begin{aligned}s\end{aligned}}$ (razen če se zgodi še ena napaka, potem se spremeni nazaj na -1).

Glej tudi

Kroneckerjev simbol, posplošitev Jacobijevega simbola na vsa cela števila.
simbol ostanka potence, posplošitev Jacobijevega simbola na ostanke višjih potenc.

Sklici

↑ Jacobi, C. G. J. (1837). »Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie«. Bericht Ak. Wiss. Berlin. str. 127–136.
↑ Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10
↑ Cohen, pp. 29–31
↑ The number field sieve, the fastest known algorithm, requires

Viri

Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. ISBN 3-540-55640-0.
Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (Second edition). New York: Springer. ISBN 0-387-97329-X.
Lemmermeyer, Franz (2000). Reciprocity Laws: from Euler to Eisenstein. Berlin: Springer. ISBN 3-540-66957-4.

Zunanje povezave

Izračunaj Jacobijev simbol pokaže korake za izvedbo računanja.

[1] Jacobi, C. G. J. (1837). »Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie«. Bericht Ak. Wiss. Berlin. str. 127–136.

[2] Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10

[3] Cohen, pp. 29–31

[4] The number field sieve, the fastest known algorithm, requires

[1]

[2]

[3]

[4]