Jacobi-szimbólum

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés]

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[szerkesztés]

  1. Ha , akkor
  2. Első kiegészítési tétel:[1]
  3. Második kiegészítési tétel:[2]
  4. Reciprocitási tétel:[3] ha P és Q relatív prím páratlan számok, akkor
  5. Ha , akkor a kvadratikus nemmaradék moduló P.[4]

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 00 01 1 −1 01 −1 −1 −1 1 01 −1 −1 −1 1 −1 1 1

Prímteszt[szerkesztés]

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.[5] 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, .[6]

Jegyzetek[szerkesztés]

  1. Forster Satz 11.7(a)
  2. Forster Satz 11.7(b)
  3. Forster Satz 11.7(c)
  4. Forster p.88
  5. Forster 12.1 Satz
  6. Forster p.93

Források[szerkesztés]