Jacobi symbol

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 mars 2020; verifiering kräver 1 redigering .

Jacobi-symbolen är en talteoretisk funktion av två argument , introducerad av C. Jacobi 1837 . Är en kvadratisk karaktär i ringen av rester .

Jacobi- symbolen generaliserar Legendre-symbolen till alla udda tal större än ett. Kronecker-Jacobi-symbolen generaliserar i sin tur Jacobi-symbolen till alla heltal , men i praktiska problem spelar Jacobi-symbolen en mycket viktigare roll än Kronecker-Jacobi-symbolen.

Definition

Låt vara ett udda tal större än ett och vara dess nedbrytning i primtalsfaktorer (det kan vara lika bland dem). Sedan, för ett godtyckligt heltal , definieras Jacobi-symbolen av likheten: $P$ ${\displaystyle P=p_{1}p_{2}\ldots p_{n))$ $p_{1},\;\ldots ,\;p_{n}$ $a$

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

var är Legendre-symbolerna . $\left(\frac{a}{p_i}\right)$

Per definition antar vi att för alla . $\left({\frac {a}{1}}\right)=1$ $a$

Egenskaper

Multipel : . $\left({\frac {ab}{P}}\right)=\left({\frac {a}{P}}\right)\left({\frac {b}{P}}\ höger)$
- I synnerhet, . $\left({\frac {a^{2}b}{P}}\right)=\left({\frac {b}{P}}\right)$
Periodicitet : om , då $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}}.$
Om är ett udda naturligt tal coprime med , då är en analog till den kvadratiska lagen om ömsesidighet . $F$ $P$ $\left({\frac {Q}{P}}\right)\left({\frac {P}{Q}}\right)=(-1)^{{\frac {P-1} {2}}\cdot {\frac {Q-1}{2}}}$
- I synnerhet om och
är coprime och udda, då . $P$ $F$ $\left({\frac {Q}{P}}\right)=(-1)^{{\frac {P-1}{2}}\cdot {\frac {Q-1}{2 ))}\left({\frac {P}{Q}}\right)$

Jacobi-symbolen är lika med tecknet på permutationen av det reducerade systemet av rester modulo , vilket ges som multiplikationen av elementen i denna grupp med (där nödvändigtvis coprime med ).

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

P

a

a

P

Viktiga anteckningar

Om datoranvändning

Jacobi-symbolen beräknas nästan aldrig per definition. Oftast används Jacobi-symbolens egenskaper för beräkningen, främst den kvadratiska ömsesidighetslagen.

Dessutom, trots att Jacobi-symbolen är en generalisering av Legendre-symbolen och definieras genom den, är det oftare Legendre-symbolen som beräknas med hjälp av Jacobi-symbolen, och inte vice versa. Se exempel

Om sambandet med kvadratiska kongruenser

Till skillnad från Legendre-symbolen kan Jacobi-symbolen inte direkt användas för att testa avgörbarheten av en kvadratisk jämförelse. Det vill säga om jämförelse ges

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

((ett))

då Jacobi-symbolen är lika med ett betyder inte alls att den givna jämförelsen är avgörbar. Till exempel, , men jämförelsen har inga lösningar (du kan kontrollera det genom uppräkning). $\left({\frac {a}{n}}\right)$ $\left({\frac {2}{15}}\right)=(-1)^{28}=1$ $x^{2}\equiv 2\mod {15}$

Men om , så har jämförelse (1) inga lösningar. $\left({\frac {a}{n}}\right)=-1$

En funktion som används i primalitetstester

I allmänhet är det inte sant att Jacobi-symbolen uppfyller samma villkor som Legendre-symbolen:

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

((2))

Till exempel,

\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 det här fallet kallas siffror som primeras med , för vilket villkor (2) inte är uppfyllt, Euler-vittnen om talets icke-enkelhet (eftersom villkor (2) är uppfyllt för ett primtal ). $7^{\frac {15-1}{2}}\equiv 7^{7}\equiv 13\mod {15}.$ $a$ $P$ $P$ $P$

Om är ett sammansatt tal , då kallas ett sådant tal för vilket villkor (2) är uppfyllt en lögnare för Euler-testet . $P$ $a$

Det är bevisat att för alla kompositer finns det högst knorrar med olika modul . $P$ $P/2$ $P$

Denna egenskap används i det probabilistiska Solovay-Strassen-testet för primalitet. I denna algoritm väljs slumpmässiga tal och villkor (2) kontrolleras för dem. Om det finns ett vittne om icke-enkelhet, är det bevisat att numret är sammansatt. Annars sägs det vara prime med viss sannolikhet . $a$ $P$ $P$

Anslutning med permutationer

Låta vara ett naturligt tal och samprima med . Kartläggningen som verkar på allt definierar en permutation vars paritet är lika med Jacobi-symbolen: $n$ $a$ $n$ $m_a: x\to ax\mod n$ $\mathbb {Z} /n\mathbb {Z}$ $\pi_a\in S_n$

$\sigma(\pi_a)=\vänster(\frac{a}{n}\höger)$ .

Applikation

I huvudsak används Jacobi-symbolen för att snabbt beräkna Legendre-symbolen .

Legendre-symbolen behövs i sin tur för att kontrollera lösbarheten av en kvadratisk kongruens modulo ett primtal. Men att räkna det per definition (det vill säga att beräkna ) är en ganska lång procedur. Med den snabba exponentieringsalgoritmen görs detta i bitvisa operationer (såvida du inte använder snabb multiplikation och division). Och beräkningen av Jacobi-symbolen kräver bara bitvisa operationer. $a^{\frac {p-1}{2}}\mod {p}$ $O(\log ^{3}p)$ $O(\log ^{2}p)$

Jacobi-symbolen används i vissa primatitetstester , till exempel i (N+1)-metoderna och, som redan nämnts , i Solovay-Strassen-testet .

Algoritm

Huvudidé

Nyckelegenskapen för Jacobi-symbolen som används i beräkningen är den kvadratiska lagen om ömsesidighet. Tack vare honom liknar algoritmen Euklids algoritm för att hitta den största gemensamma delaren av två tal, där argumenten också byts om i varje steg. I likhet med Euklids algoritm , när argumenten omarrangeras, ersätts det större av resten av divisionen med det mindre. Detta är möjligt på grund av Jacobi-symbolens periodicitet . Men eftersom Jacobi-symbolen endast definieras om det andra argumentet är udda, allokeras den jämna delen av det första argumentet före permutationen.

Formell beskrivning

Indata: a — heltal, b — positivt heltal, udda, större än ett.

Utgång: - Jacobi symbol $\left(\frac{a}{b}\right)$

1 (enkelhetstest). Om gcd ( a , b )≠1, avsluta algoritmen med svaret 0 . 2 (initiering). r :=1 3 (övergång till positiva tal). Om a<0 så är a:=-a Om b mod 4 = 3 så r:=-r End if 4 (att bli av med paritet). t :=0 Medan cykel a är jämn t:=t+1 a:=a/2 Slut på cykel Om t är udda, då Om b mod 8 = 3 eller 5, då r :=- r . Sluta om 5 (kvadratisk lag om ömsesidighet). Om a mod 4 = b mod 4 = 3, då r :=- r . c:=a; a:=b mod c; b:=c. 6 (utanför algoritmen?). Om a ≠ 0, gå sedan till steg 4, annars avsluta algoritmen med svaret r .

Kommentarer till algoritmen

I algoritmen tas den minsta positiva resten (det vill säga resten av divisionen) överallt.

I det fjärde steget används multiplikativiteten för Jacobi-symbolen, och sedan beräknas Jacobi-symbolen . För att undvika onödig exponentiering kontrolleras endast resten av divisionen med 8. $\left({\frac {2}{b}}\right)=(-1)^{(b^{2}-1)/8}$ $b$

I det femte steget, istället för att höja till en makt, används också kontroll av resten av divisionen.

Algoritmens komplexitet är lika med bitoperationer. $O(\log {a}\cdot \log {b})$

Beräkningsexempel

Beräkna Legendre-symbolen med hjälp av Jacobi-symbolen:

\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.

Referenser

Vasilenko O.N. Talteoretiska algoritmer i kryptografi. - Moskva: MTsMNO, 2003. - S. 328. - ISBN 5-94057-103-4 . .
Vinogradov I.M. Grunderna i talteorin . - 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 . .

Karaktärer i talteori och i gruppteori
Kvadratiska tecken	Symbol för Legendre Jacobi symbol Kronecker symbol - Jacobi
Karaktärer av kraftrester	Den kubiska återstodens natur Den biquadratiska restens natur Symbol för kraftrester