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{\pmod {P}}$, akkor ${\bigg (}{\frac {a}{P}}{\bigg )}={\bigg (}{\frac {b}{P}}{\bigg )}$
2. $\left({\frac {1}{P}}\right)=1$
3. ${\bigg (}{\frac {ab}{P}}{\bigg )}={\bigg (}{\frac {a}{P}}{\bigg )}{\bigg (}{\frac {b}{P}}{\bigg )}$
4. Első kiegészítési tétel:

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

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

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

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

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

7. Ha ${\bigg (}{\frac {a}{P}}{\bigg )}=-1$, akkor a kvadratikus nemmaradék moduló P.

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

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

A következő táblázat az $\left({\frac {a}{P}}\right)$ Jacobi-szimbólum értékeit tartalmazza $3\leq P\leq 17$ és $0\leq a\leq 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	00	01	1	−1	01	−1	−1	−1	1	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}}{\pmod {p}}$

A Jacobi-szimbólumra igaz ennek megfordítása: ha $P\geq 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}}{\pmod {P}}$,

akkor P egy prímszám. 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\leq 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}$.

Források

• ↑ Forster: Otto Forster. Algorithmische Zahlentheorie, 2 (német nyelven), Springer Spektrum Wiesbaden. DOI: 10.1007/978-3-658-06540-9 (2015). ISBN 978-3-658-06540-9 
• Algoritmusok - Márton Gyöngyvér (ms.sapientia.ro)