Jacobi symbol

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 19. marts 2020; verifikation kræver 1 redigering .

Jacobi-symbolet er en talteoretisk funktion af to argumenter , introduceret af C. Jacobi i 1837 . Er et kvadratisk tegn i ringen af rester .

Jacobi- symbolet generaliserer Legendre-symbolet til alle ulige tal større end et. Kronecker-Jacobi-symbolet generaliserer til gengæld Jacobi-symbolet til alle heltal , men i praktiske problemer spiller Jacobi-symbolet en meget vigtigere rolle end Kronecker-Jacobi-symbolet.

Definition

Lad være et ulige tal større end et og være dets nedbrydning i primfaktorer (der kan være lige blandt dem). Derefter, for et vilkårligt heltal , er Jacobi-symbolet defineret af ligheden: $P$ ${\displaystyle P=p_{1}p_{2}\ldots p_{n))$ $p_{1},\;\ldots ,\;p_{n}$ $-en$

\left({\frac {a}{P}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_ {2}}}\right)\cdots \left({\frac {a}{p_{n}}}\right),

hvor er Legendre-symbolerne . $\left(\frac{a}{p_i}\right)$

Per definition antager vi, at for alle . $\left({\frac {a}{1}}\right)=1$ $-en$

Egenskaber

Multiplikitet :. _ $\left({\frac {ab}{P}}\right)=\left({\frac {a}{P}}\right)\left({\frac {b}{P}}\ ret)$
- Især . $\left({\frac {a^{2}b}{P}}\right)=\left({\frac {b}{P}}\right)$
Periodicitet : hvis , så $a\equiv b{\pmod {P}}$ $\left({\frac {a}{P}}\right)=\left({\frac {b}{P}}\right);$
$\left({\frac {1}{P}}\right)=1;$
$\left({\frac {-1}{P}}\right)=(-1)^{\frac {P-1}{2));$
$\left({\frac {2}{P}}\right)=(-1)^{\frac {P^{2}-1}{8}}.$
Hvis er et ulige naturligt tal coprime med , så er en analog til den kvadratiske lov om gensidighed . $Q$ $P$ $\left({\frac {Q}{P}}\right)\left({\frac {P}{Q}}\right)=(-1)^{{\frac {P-1} {2}}\cdot {\frac {Q-1}{2}}}$
- Især hvis og
er coprime og ulige, så . $P$ $Q$ $\left({\frac {Q}{P}}\right)=(-1)^{{\frac {P-1}{2}}\cdot {\frac {Q-1}{2 ))}\venstre({\frac {P}{Q}}\right)$

Jacobi-symbolet er lig med tegnet på permutationen af det reducerede system af rester modulo , som er givet som multiplikationen af elementerne i denne gruppe med (hvor nødvendigvis coprime med ).

\left({\frac {a}{P}}\right)

P

-en

-en

P

Vigtige bemærkninger

Om computing

Jacobi-symbolet beregnes næsten aldrig per definition. Oftest bruges Jacobi-symbolets egenskaber til beregningen, hovedsageligt den kvadratiske reciprocitetslov.

På trods af at Jacobi-symbolet er en generalisering af Legendre-symbolet og defineres gennem det, er det desuden oftere Legendre-symbolet, der beregnes ved hjælp af Jacobi-symbolet, og ikke omvendt. Se eksempel

Om forbindelsen med kvadratiske kongruenser

I modsætning til Legendre-symbolet kan Jacobi-symbolet ikke bruges direkte til at teste afgøreligheden af en kvadratisk sammenligning. Altså hvis sammenligning er givet

x^{2}\equiv a\mod n,

((en))

så betyder det, at Jacobi-symbolet er lig med én , slet ikke, at den givne sammenligning kan afgøres. For eksempel, , men sammenligningen har ingen løsninger (du kan kontrollere det ved opregning). $\left({\frac {a}{n))\right)$ $\left({\frac {2}{15}}\right)=(-1)^{28}=1$ $x^{2}\equiv 2\mod {15}$

Men hvis , så har sammenligning (1) ingen løsninger. $\left({\frac {a}{n}}\right)=-1$

En funktion, der bruges i primalitetstests

Generelt er det ikke rigtigt, at Jacobi-symbolet opfylder samme betingelse som Legendre-symbolet:

\left({\frac {a}{P}}\right)\equiv a^{\frac {P-1}{2}}\mod P.

((2))

For eksempel,

\left({\frac {7}{15}}\right)=\left({\frac {7}{5}}\right)\cdot \left({\frac {7}{3} }\right)=\left({\frac {2}{5}}\right)\cdot \left({\frac {1}{3}}\right)=(-1)^{\frac {25 -1}{8}}\cdot 1=-1.

I dette tilfælde kaldes tal coprime med , for hvilke betingelse (2) ikke er opfyldt, Euler vidner om tallets uenkelhed (da betingelse (2) er opfyldt for et primtal ). $7^{\frac {15-1}{2}}\equiv 7^{7}\equiv 13\mod {15}.$ $-en$ $P$ $P$ $P$

Hvis er et sammensat tal , kaldes et sådant tal, for hvilket betingelse (2) er opfyldt, en løgner for Euler-testen . $P$ $-en$

Det er bevist, at der for ethvert kompositmateriale højst er knogler med forskellig modul . $P$ $P/2$ $P$

Denne egenskab bruges i den probabilistiske Solovay-Strassen-test for primalitet. I denne algoritme vælges tilfældige tal, og betingelse (2) kontrolleres for dem. Hvis der er et vidnesbyrd om ikke-enkelhed, så er det bevist, at tallet er sammensat. Ellers siges det at være prime med en vis sandsynlighed . $-en$ $P$ $P$

Forbindelse med permutationer

Lade være et naturligt tal og coprime med . Kortlægningen , der virker på alt, definerer en permutation , hvis paritet er lig med Jacobi-symbolet: $n$ $-en$ $n$ $m_a: x\til ax\mod n$ $\mathbb {Z} /n\mathbb {Z}$ $\pi_a\i S_n$

$\sigma(\pi_a)=\venstre(\frac{a}{n}\højre)$ .

Ansøgning

Hovedsageligt bruges Jacobi-symbolet til hurtigt at beregne Legendre-symbolet .

Legendre-symbolet er til gengæld nødvendigt for at kontrollere løseligheden af en kvadratisk kongruens modulo et primtal. Men at tælle det per definition (det vil sige at beregne ) er en ret lang procedure. Med den hurtige eksponentieringsalgoritme gøres dette i bitvise operationer (medmindre du bruger hurtig multiplikation og division). Og beregningen af Jacobi-symbolet kræver kun bitvise operationer. $a^{\frac {p-1}{2}}\mod {p}$ $O(\log ^{3}p)$ $O(\log ^{2}p)$

Jacobi-symbolet bruges i nogle primalitetstests , for eksempel i (N+1)-metoderne og, som allerede nævnt , i Solovay-Strassen-testen .

Algoritme

Hovedidé

Nøgleegenskaben for Jacobi-symbolet brugt i beregningen er den kvadratiske lov om gensidighed. Takket være ham ligner algoritmen Euklids algoritme til at finde den største fælles divisor af to tal, hvor argumenterne også byttes om ved hvert trin. I lighed med Euklids algoritme , når argumenterne omarrangeres, erstattes det større med resten af divisionen med det mindre. Dette er muligt på grund af Jacobi-symbolets periodicitet . Men da Jacobi-symbolet kun er defineret, hvis det andet argument er ulige, allokeres den lige del af det første argument før permutationen.

Formel beskrivelse

Inputdata: a — heltal, b — positivt heltal, ulige, større end én.

Output: - Jacobi symbol $\left(\frac{a}{b}\right)$

1 (simpelhedstest). Hvis gcd ( a , b )≠1, forlad algoritmen med svaret 0 . 2 (initialisering). r :=1 3 (overgang til positive tal). Hvis a<0 så er a:=-a Hvis b mod 4 = 3 så r:=-r End if 4 (at slippe af med paritet). t :=0 Mens cyklus a er lige t:=t+1 a:=a/2 Slut på cyklus Hvis t er ulige, så hvis b mod 8 = 3 eller 5, så r :=- r . Afslut Hvis 5 (kvadratisk lov om gensidighed). Hvis a mod 4 = b mod 4 = 3, så r :=- r . c:=a; a:=b mod c; b:=c. 6 (ud af algoritmen?). Hvis a ≠ 0, så gå til trin 4, ellers forlad algoritmen med svaret r .

Kommentarer til algoritmen

I algoritmen tages den mindste positive rest (det vil sige resten af divisionen) overalt.

I det fjerde trin bruges multiplikativiteten af Jacobi-symbolet, og derefter beregnes Jacobi-symbolet . For at undgå unødvendig eksponentiering er kun resten af division med 8 markeret. $\left({\frac {2}{b}}\right)=(-1)^{(b^{2}-1)/8}$ $b$

På det femte trin, i stedet for at hæve til en potens, bruges også kontrol af resten af divisionen.

Algoritmens kompleksitet er lig med bitoperationer. $O(\log {a}\cdot \log {b})$

Beregningseksempel

Beregning af Legendre-symbolet ved hjælp af Jacobi-symbolet:

\left({\frac {219}{383}}\right)=-\left({\frac {383}{219}}\right)=-\left({\frac {164}{219 }}\right)=-\left({\frac {41}{219}}\right)=-\left({\frac {219}{41}}\right)=-\left({\frac { 14}{41}}\right)=

=-\left({\frac {2}{41}}\right)\left({\frac {7}{41}}\right)=-\left({\frac {7}{41 }}\right)=-\left({\frac {41}{7}}\right)=-\left({\frac {-1}{7}}\right)=1.

Referencer

Vasilenko O.N. Talteoretiske algoritmer i kryptografi. - Moskva: MTsMNO, 2003. - S. 328. - ISBN 5-94057-103-4 . .
Vinogradov I.M. Grundlæggende om talteori . - Moskva: GITTL, 1952. - S. 180. - ISBN 5-93972-252-0 .
Bach E., Shallit J. Algoritmisk talteori. Vol. I. - Massachusetts: MIT Press, 1996. - ISBN 0-262-02405-5 . .

Karakterer i talteori og i gruppeteori
Kvadratiske tegn	Symbol for Legendre Jacobi symbol Kronecker symbol - Jacobi
Karakterer af kraftrester	Arten af den kubiske rest Naturen af den biquadratiske rest Symbol for strømrester