Jacobijev simbol

Predloga:Diagonal split header	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 Predloga:Veliko Predloga:Sfrac Predloga:Veliko za različne k (proti vrhu) in n (proti levi). Prikazani so samo Predloga:Brez preloma, 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 Predloga:Brez preloma, a niso vsi vnosi Jacobijevega simbola 1 (glej vrsti Predloga:Brez preloma in Predloga:Brez preloma) kvadratni ostanki. Opazimo tudi, da če je eden izmed n ali k kvadrat, so vse vrednosti nenegativne.

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.

Definicija

Za katerokoli celo število a in liho naravno število n, je Jacobijev simbol Predloga:Veliko Predloga:Sfrac Predloga:Veliko definiran kot produkt Legendrovih simbolov, ki predstavljajo praštevilski razcep od n:

(\frac{a}{n}) = {(\frac{a}{p_{1}})}^{α_{1}} {(\frac{a}{p_{2}})}^{α_{2}} \dots {(\frac{a}{p_{k}})}^{α_{k}},

kjer je

n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{k}^{α_{k}}

praštevilski razcep od n.

Legendrov simbol Predloga:Veliko Predloga:Sfrac Predloga:Veliko je za vsa cela števila a in vsa liha praštevila p definiran

(\frac{a}{p}) = {\begin{matrix} 0 & če a \equiv 0 (\mod p), \\ 1 & če a \equiv̸ 0 (\mod p) in za neko celo število x : a \equiv x^{2} (\mod p), \\ - 1 & če a \equiv̸ 0 (\mod p) in ne obstaja noben tak x . \end{matrix}

Po standardnem sporazumu za prazni produkt, velja Predloga:Veliko Predloga:Sfrac Predloga:Veliko = 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 Predloga:Veliko Predloga:Sfrac Predloga:Veliko za n ≤ 59, k ≤ 30, n je lih.

Predloga:Diagonal split header	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 Predloga:Veliko Predloga:Sfrac Predloga:Veliko enak (in zapisan enako kot) pripadajoči Legendrov simbol.

2. Če je Predloga:Brez preloma, potem je

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

3.

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

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

4.

(\frac{a b}{n}) = (\frac{a}{n}) (\frac{b}{n}), torej (\frac{a^{2}}{n}) = {(\frac{a}{n})}^{2} = 1 ali 0 .

5.

(\frac{a}{m n}) = (\frac{a}{m}) (\frac{a}{n}), torej (\frac{a}{n^{2}}) = {(\frac{a}{n})}^{2} = 1 ali 0 .

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

6.

(\frac{m}{n}) (\frac{n}{m}) = (- 1)^{\frac{m - 1}{2} \cdot \frac{n - 1}{2}} = {\begin{matrix} 1 & če n \equiv 1 (\mod 4) ali m \equiv 1 (\mod 4), \\ - 1 & če n \equiv m \equiv 3 (\mod 4) \end{matrix}

7.

(\frac{- 1}{n}) = (- 1)^{\frac{n - 1}{2}} = {\begin{matrix} 1 & če n \equiv 1 (\mod 4), \\ - 1 & če n \equiv 3 (\mod 4), \end{matrix}

in to se da prepisati v

8.

(\frac{2}{n}) = (- 1)^{\frac{n^{2} - 1}{8}} = {\begin{matrix} 1 & če n \equiv 1, 7 (\mod 8), \\ - 1 & če n \equiv 3, 5 (\mod 8) . \end{matrix}

9.

(\frac{2 a}{n}) = (\frac{2}{n}) (\frac{a}{n}) = {\begin{matrix} (\frac{a}{n}) & če n \equiv 1, 7 (\mod 8), \\ - (\frac{a}{n}) & če n \equiv 3, 5 (\mod 8) . \end{matrix}

Če združimo lastnosti 4 in 8 dobimo:

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

Kot Legendrov simbol:

Če je Predloga:Veliko Predloga:Sfrac Predloga:Veliko = −1 potem je a kvadratni modulo n brez ostanka.

Če je a kvadratni ostanek modula n in D(a,n) = 1, potem Predloga:Veliko Predloga:Sfrac Predloga:Veliko = 1.

A za razliko od Legendrovega simbola:

Če je Predloga:Veliko Predloga:Sfrac Predloga:Veliko = 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 Predloga:Veliko Predloga:Sfrac Predloga:Veliko je Dirichletov znak k modulom n.

Izračunavanje Jacobijevega simbola

Zgornje formule vodijo v učinkoviti algoritem Predloga:Brez preloma^[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 Predloga:Veliko Predloga:Sfrac Predloga:Veliko je definiran le za liha praštevila p. Upošteva enaka pravila kot Jacobijev simbol (torej recipročnost in suplementarne formule za Predloga:Veliko Predloga:Sfrac Predloga:Veliko in Predloga:Veliko Predloga:Sfrac Predloga:Veliko ter multiplikativnost števca.)

Problem: Če je 9907 praštevilo, izračunaj Predloga:Veliko Predloga:Sfrac Predloga:Veliko.

Z uporabo Legendrovega simbola

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

Z uporabo Jacobijevega simbola

\begin{matrix} (\frac{19}{45}) & = 1 & in & 1 9^{\frac{45 - 1}{2}} & \equiv 1 (\mod 45) . \\ (\frac{8}{21}) & = - 1 & toda & 8^{\frac{21 - 1}{2}} & \equiv 1 (\mod 21) . \\ (\frac{5}{21}) & = 1 & toda & 5^{\frac{21 - 1}{2}} & \equiv 16 (\mod 21) . \end{matrix}

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{matrix} (\frac{19}{45}) & = 1 & in & 1 9^{\frac{45 - 1}{2}} & \equiv 1 (\mod 45) . \\ (\frac{8}{21}) & = - 1 & toda & 8^{\frac{21 - 1}{2}} & \equiv 1 (\mod 21) . \\ (\frac{5}{21}) & = 1 & toda & 5^{\frac{21 - 1}{2}} & \equiv 16 (\mod 21) . \end{matrix}

Torej če je znano, ali je število n praštevilo ali sestavljeno število, lahko izberemo naključno število a, izračunamo Jacobijev simbol Predloga:Veliko Predloga:Sfrac Predloga:Veliko 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{matrix} 2^{82, 589, 933} - 1 \end{matrix}$ (največje znano Mersennovo število (decembra 2018). V posebnem primeru, je Jacobijev simbol:

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

To drži tudi za končni ostanek $\begin{matrix} s_{p - 2} \end{matrix}$ 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{matrix} s \end{matrix}$ (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

Predloga:Sklici

Viri

Zunanje povezave

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

↑ Predloga:Navedi revijo
↑ Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10
↑ Cohen, pp. 29–31
↑ The number field sieve, the fastest known algorithm, requires

[1] Predloga:Navedi revijo

[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]

Jacobijev simbol

Vsebina

Definicija

Tabela vrednosti

Lastnosti

Izračunavanje Jacobijevega simbola

Implementacija v jeziku Lua

Primeri računanja

Z uporabo Legendrovega simbola

Z uporabo Jacobijevega simbola

Praštevilski test

Glej tudi

Sklici

Viri

Zunanje povezave

Navigacijski meni

Jacobijev simbol

Definicija

Tabela vrednosti

Lastnosti

Izračunavanje Jacobijevega simbola

Implementacija v jeziku Lua

Primeri računanja

Z uporabo Legendrovega simbola

Z uporabo Jacobijevega simbola

Praštevilski test

Glej tudi

Sklici

Viri

Zunanje povezave

Navigacijski meni

Iskanje