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áratlan szám, a hozzá relatív prím egész, akkor

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

Tulajdonságai Ha , akkor

Első kiegészítési tétel:

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

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

Ha , akkor a kvadratikus nemmaradék moduló P. Ha viszont , abból nem következik, hogy a kvadratikus maradék lenne moduló P: 2 például kvadratikus nemmaradék moduló 15, viszont

A következő táblázat az Jacobi-szimbólum értékeit tartalmazza és 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 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 0 1 1 −1 1 −1 −1 −1 1 1 −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

A Jacobi-szimbólumra igaz ennek megfordítása: ha páratlan szám, és valamennyi maradékosztályra teljesül, hogy , 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 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, .

Jegyzetek

Források

Algoritmusok - Márton Gyöngyvér (ms.sapientia.ro)

Kategória:Számelmélet