01234567891011121314151611301−1501−1−117011−11−1−190110110111101−1111−1−1−11−11301−111−1−1−1−111−11150110100−1100−10−1−117−0−11−1−1−1−1−11−1−1−1−11−111 Jacobijev simbol za različne k (proti vrhu) in n (proti levi). Prikazani so samo , 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 , a niso vsi vnosi Jacobijevega simbola 1 (glej vrsti in ) 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, 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 definiran kot produkt Legendrovih simbolov, ki predstavljajo praštevilski razcep od n:

kjer je

praštevilski razcep od n.

Legendrov simbol je za vsa cela števila a in vsa liha praštevila p definiran

Po standardnem sporazumu za prazni produkt, velja = 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 za n ≤ 59, k ≤ 30, n je lih. 1234567891011121314151617181920212223242526272829301−111−11111−1111111−111111111−11111131−101−101−101−101−101−101−101−101−101−1051−1−1101−1−1101−1−1101−1−1101−1−1101−1−110711−11−1−1011−11−1−1011−11−1−1011−11−1−10119110110110110110110110110110110111−1111−1−1−11−101−1111−1−1−11−101−1111−1−1−1131−111−1−1−1−111−1101−111−1−1−1−111−1101−11115110100−1100−10−1−10110100−1100−10−1−101711−11−1−1−111−1−1−11−111011−11−1−1−111−1−1−11191−1−11111−11−11−1−1−1−111−101−1−11111−11−11211−101100−10−1−10−100110−1101−101100−10231111−11−111−1−111−1−11−11−1−1−1−101111−11−125111101111011110111101111011110271−101−101−101−101−101−101−101−101−101−10291−1−11111−11−1−1−11−1−11−1−1−11−11111−1−11013111−111−11111−1−1−11−11−1111−1−1−1−11−1−11−1−1331101−10−110−100−1−10110−1−100−101−10−110351−1110−10−1101110011−1−100−1−1−10−11010371−111−1−11−11111−1−1−11−1−1−1−11−1−1−11111−1139110110−1101100−101−10−1101−10100−1−104111−111−1−1111−1−1−1−1−11−11−111−11−11−1−1−1−1−1431−1−11−11−1−1111−111111−1−1−11−1111−1−1−1−1−1451−10100−1−10010−1101−10100−1−10010−110471111−11111−1−11−11−1111−1−11−1−111−111−1−149111111011111101111110111111011511−10110−1−10−110110100110−1101−10−110531−1−11−111−1111−11−1111−1−1−1−1−1−111−1−111−15511−110−111100−1110111−10−10−1−101−11−10571101−10110−1−10−1101−100−10−1−101−10110591−1111−11−11−1−11−1−1111−11111−1−111111−1

Lastnosti Sledeča dejstva, celo obratni zakoni, so direktne dedukcije iz definicije Jacobijevega simbola in pripadajočih lastnosti Legendrovega simbola.Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10

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 enak (in zapisan enako kot) pripadajoči Legendrov simbol.

2. Če je , potem je

3.

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

4.

5.

Zakon kvadratne recipročnosti: če sta si m in n lihi tuji naravni števili, potem je

6.

7.

in to se da prepisati v

8.

9.

Če združimo lastnosti 4 in 8 dobimo:

Kot Legendrov simbol:

Če je  = −1 potem je a kvadratni modulo n brez ostanka.

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

A za razliko od Legendrovega simbola:

Če je  = 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 lemi Zolotarjova.

Jacobijev simbol je Dirichletov znak k modulom n.

Izračunavanje Jacobijevega simbola Zgornje formule vodijo v učinkoviti algoritem Cohen, pp. 29–31 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 je definiran le za liha praštevila p. Upošteva enaka pravila kot Jacobijev simbol (torej recipročnost in suplementarne formule za in ter multiplikativnost števca.)

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

Z uporabo Legendrovega simbola

Z uporabo Jacobijevega simbola

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.The number field sieve, the fastest known algorithm, requires 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

Torej če je znano, ali je število n praštevilo ali sestavljeno število, lahko izberemo naključno število a, izračunamo Jacobijev simbol 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 (največje znano Mersennovo število (decembra 2018). V posebnem primeru, je Jacobijev simbol:

To drži tudi za končni ostanek 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 (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

Viri

Zunanje povezave

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

Kategorija:Modularna aritmetika