Jacobi-szimbólum

A számelméletben a Jacobi-szimbólum a Legendre-szimbólum általánosítása. Szerepet játszik prímteszt- és prímfelbontási algoritmusokban, és így jelentőséggel bír a kriptográfia számára is. Carl Gustav Jacob Jacobi matematikusról van elnevezve.

Definíciója

Ha $P>2$ páratlan szám, a hozzá relatív prím egész, akkor

$\left(\frac{a}{P}\right)={\left(\frac{a}{p_1}\right)}^{{\alpha }_1}{\left(\frac{a}{p_2}\right)}^{{\alpha }_2}\cdots {\left(\frac{a}{p_k}\right)}^{{\alpha }_k}$

ahol $P=p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k}$ a prímhatványfelbontás, és a jobb oldalon Legendre-szimbólumok állnak. Ha a-nak és P-nek van 1-nél nagyobb közös osztója, akkor $\left(\frac{a}{P}\right)=0$.

Tulajdonságai

1. Ha $a\equiv b(\mathrm{mod}P)$, akkor $\left(\frac{a}{P}\right)=\left(\frac{b}{P}\right)$
2. $\left(\frac{1}{P}\right)=1$
3. $\left(\frac{ab}{P}\right)=\left(\frac{a}{P}\right)\left(\frac{b}{P}\right)$
4. Első kiegészítési tétel:Sablon:Refhely

   $\left(\frac{-1}{P}\right)=(-1{)}^{\frac{P-1}{2}}$

5. Második kiegészítési tétel:Sablon:Refhely

   $\left(\frac{2}{P}\right)=(-1{)}^{\frac{P^2-1}{8}}$

6. Reciprocitási tétel:Sablon:Refhely ha P és Q relatív prím páratlan számok, akkor

   $\left(\frac{P}{Q}\right)=\left(\frac{Q}{P}\right)(-1{)}^{\frac{(P-1)(Q-1)}{4}}$

7. Ha $\left(\frac{a}{P}\right)=-1$, akkor a kvadratikus nemmaradék moduló P.Sablon:Refhely

Ha viszont $\left(\frac{a}{P}\right)=1$, abból nem következik, hogy a kvadratikus maradék lenne moduló P: 2 például kvadratikus nemmaradék moduló 15, viszont

$\left(\frac{2}{15}\right)=\left(\frac{2}{3}\right)\cdot \left(\frac{2}{5}\right)=(-1)\cdot (-1)=1$

A következő táblázat az $\left(\frac{a}{P}\right)$ Jacobi-szimbólum értékeit tartalmazza $3\le P\le 17$ és $0\le a\le 16$ esetén: az első oszlop P értékeiből, az első sor a értékeiből áll. A sárga színnel kiemelt cellák azon $(a,P)$ pároknak felelnek meg, amikre a kvadratikus maradék moduló P. Az üres cellák értéket a fenti 1. tulajdonság alapján visszavezethetők a kitöltött cellákban szereplő értékekre.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
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	Sablon:00	Sablon:01	1	−1	Sablon:01	−1	−1	−1	1	Sablon:01	−1	−1	−1	1	−1	1	1

Prímteszt

A Legendre-szimbólumra vonatkozó Euler-kritérium kimondja, hogy ha p egy páratlan prímszám és a egy egész szám, akkor

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)$

A Jacobi-szimbólumra igaz ennek megfordítása: ha $P\ge 3$ páratlan szám, és valamennyi $a\in (\mathbb{Z}/P\mathbb{Z}{)}^{\times }$ maradékosztályra teljesül, hogy

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

akkor P egy prímszám.Sablon:Refhely A Jacobi-szimbólum ezen tulajdonsága tehát alkalmas annak eldöntésére, hogy egy adott P szám prímszám-e.

A Solovay–Strasser-prímteszt a kritérium iteratív alkalmazásából áll: egy véletlenszerűen választott $2\le a<P$ számra ellenőrizzük, hogy a fenti kongruencia teljesül-e. Ha nem, akkor P nem prímszám. Ha igen, akkor választunk egy újabb a számot, és arra is ellenőrizzük a kongruenciát. Ha k különböző a-ra teljesül a kongruencia, akkor annak valószínűsége, hogy P mégsem prímszám, $2^{-k}$.Sablon:Refhely

Források

• Sablon:Hely Sablon:Cite book
• Algoritmusok - Márton Gyöngyvér (ms.sapientia.ro)