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.

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

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle \left({\frac {a}{P}}\right)=0}$ .

1. Ha ${\displaystyle a\equiv b{\pmod {P}}}$ , akkor ${\displaystyle {\bigg (}{\frac {a}{P}}{\bigg )}={\bigg (}{\frac {b}{P}}{\bigg )}}$ 
2. ${\displaystyle \left({\frac {1}{P}}\right)=1}$ 
3. ${\displaystyle {\bigg (}{\frac {ab}{P}}{\bigg )}={\bigg (}{\frac {a}{P}}{\bigg )}{\bigg (}{\frac {b}{P}}{\bigg )}}$ 
4. Első kiegészítési tétel:
   ${\displaystyle {\bigg (}{\frac {-1}{P}}{\bigg )}=(-1)^{\frac {P-1}{2}}}$ 
5. Második kiegészítési tétel:
   ${\displaystyle \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
   ${\displaystyle {\bigg (}{\frac {P}{Q}}{\bigg )}={\bigg (}{\frac {Q}{P}}{\bigg )}(-1)^{\frac {(P-1)(Q-1)}{4}}}$ 
7. Ha ${\displaystyle {\bigg (}{\frac {a}{P}}{\bigg )}=-1}$ , akkor a kvadratikus nemmaradék moduló P.

Ha viszont ${\displaystyle {\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

${\displaystyle {\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 ${\displaystyle \left({\frac {a}{P}}\right)}$  Jacobi-szimbólum értékeit tartalmazza ${\displaystyle 3\leq P\leq 17}$  és ${\displaystyle 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 ${\displaystyle (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.

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

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

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

${\displaystyle \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 ${\displaystyle 2\leq a$  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, ${\displaystyle 2^{-k}}$ .

• ↑ 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)