Kronecker symbol - Jacobi

Kronecker-Jacobi-symbolen är en funktion som används i talteorin . Kallas ibland Legendre-Jacobi-Kronecker- symbolen eller helt enkelt Kronecker-symbolen .

Kronecker-Jacobi-symbolen är en generalisering av Legendre- och Jacobi -symbolerna . Legendre-symbolen definieras endast för primtal, Jacobi -symbolen definieras för naturliga udda tal, och Kronecker-Jacobi-symbolen utökar detta koncept till alla heltal.

Definition

Kronecker-Jacobi-symbolen definieras enligt följande: $\left(\frac{a}{b}\right)$

om är ett udda primtal, då sammanfaller Kronecker-Jacobi-symbolen med Legendre-symbolen ; $b$
om , då $b=0$ $\left({\frac {a}{0}}\right)={\begin{cases}1,&{\text{if}}\ a=\pm 1,\\0,&{\ text{om}}\ a\neq \pm 1;\end{cases}}$
om , då $b=2$ $\left({\frac {a}{2}}\right)={\begin{cases}0,&{\text{if}}\ a\equiv 0{\pmod {2}},\ \(-1)^{\frac {a^{2}-1}{8)),&{\text{if))\ a\equiv 1{\pmod {2));\end{case))$
om , då $b=-1$ $\left({\frac {a}{-1}}\right)={\begin{cases}-1,&{\text{if}}\ a<0,\\1,&{\ text{if}}\ a\geqslant 0;\end{cases}}$
om , där , är enkla (inte nödvändigtvis distinkta), då $b=\delta\cdot p_1\cdot\ldots\cdot p_n$ $\delta=\pm 1$ $p_{1},\;\ldots ,\;p_{n}$

\left({\frac {a}{b}}\right)=\left({\frac {a}{\delta }}\right)\cdot \left({\frac {a}{p_ {1}}}\right)\cdots \left({\frac {a}{p_{n}}}\right),

där det definieras ovan. $\left(\frac{a}{p_i}\right)$

Egenskaper

$\left(\frac{a}{b}\right)=0$ om och bara om ( och inte är coprime ). $(a,\;b)\nev 1$ $a$ $b$
Multipel : . $\left(\frac{ab}{c}\right)=\left(\frac{a}{c}\right)\left(\frac{b}{c}\right)$
- I synnerhet, . $\left(\frac{a^2b}{c}\right)=\left(\frac{b}{c}\right)$
Periodicitet med avseende på variabeln : om , då $a$ $b>0$
- när perioden är , det vill säga ; $b\not \equiv 2{\pmod {4}}$ $b$ $\left(\frac{a+b}{b}\right)=\left(\frac{a}{b}\right)$
- när perioden är , dvs . $b\equiv 2{\pmod {4}}$ $4b$ $\left(\frac{a+4b}{b}\right)=\left(\frac{a}{b}\right)$
Periodicitet med avseende på variabeln : om , då $b$ $a\neq 0$
- när perioden är , det vill säga ; $a\equiv 0;\;1{\pmod {4}}$ $|a|$ $\left(\frac{a}{b+\left|a\right |}\right)=\left(\frac{a}{b}\right)$
- när perioden är , dvs . $a\equiv 2;\;3{\pmod {4}}$ $4|a|$ $\left(\frac{a}{b+4\left|a\right |}\right)=\left(\frac{a}{b}\right)$
Om är ett udda naturligt tal, gäller Jacobi-symbolens egenskaper: $b$
- $\left(\frac{1}{b}\right)=1;$
- $\left(\frac{-1}{b}\right)=(-1)^{\frac{b-1}{2}});$
- $\left(\frac{2}{b}\right)=(-1)^{\frac{b^2-1}{8}}.$
En analog till den kvadratiska lagen om ömsesidighet : om är udda naturliga tal, då . $A,\;B$ $\left(\frac{A}{B}\right)\left(\frac{B}{A}\right)=(-1)^{\frac{A-1}{2}\cdot\frac{ B-1}{2}}$

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})=\left({\frac {a}{n}}\right).

Beräkningsalgoritm

1. (Fall b=0 ) Om då

b=0

Om , gå ur algoritmen med svar 1

|a|=1

Om , gå ur algoritmen med svaret 0

|a|\neq1

Avsluta If 2. (Även b ) Om a och b båda är jämna, avsluta algoritmen och returnera 0

v=0

Medan loop b är jämn

v:=v+1; b:=b/2

Slut på cykeln Om v är jämnt så är k=1 annars

k=(-1)^{\frac{a^2-1}{8}}

Om , då

b<0

b:=-b

Om , då

a<0

k:=-k

Avsluta If 3. (Lämnar algoritmen?) Om , då

a=0

Om , gå ur algoritmen med svaret 0

b>1

Om , då utgången från algoritmen med svaret k

b=1

Avsluta If

v:=0

Slinga medan a är jämnt

v:=v+1; a:=a/2

Slut på cykeln Om v är udda, då

k:=(-1)^{\frac{b^2-1}{8}}k

4. (Tillämpning av den kvadratiska lagen om ömsesidighet)

k:=k(-1) ^{\frac{(a-1)(b-1)}{4))

r:=|a|

a:=b\mod{r}

(minst positiva avdrag)

b:=r

Gå till steg 3

Obs: för beräkningen behöver du inte beräkna exponenten, det räcker med att veta resten av divisionen med 8. Detta ökar hastigheten på algoritmen. $(-1)^{\frac{a^2-1}{8}}$ $a$

Referenser

Vinogradov I.M. Grunderna i talteorin . - Moskva: GITTL, 1952. - S. 180. - ISBN 5-93972-252-0 .
N. Cohen. En kurs i beräkningsalgebraisk talteori. - Springer, 1996. - ISBN 3-540-55640-0 .

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