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 {\displaystyle P>2} páratlan szám, a hozzá relatív prím egész, akkor

( a P ) = ( a p 1 ) α 1 ( a p 2 ) α 2 ⋯ ( a p k ) α k {\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 P = p 1 α 1 ⋯ p k α k {\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 ( a P ) = 0 {\displaystyle \left({\frac {a}{P}}\right)=0} .

Tulajdonságai

  1. Ha a ≡ b ( mod P ) {\displaystyle a\equiv b{\pmod {P}}} , akkor ( a P ) = ( b P ) {\displaystyle {\bigg (}{\frac {a}{P}}{\bigg )}={\bigg (}{\frac {b}{P}}{\bigg )}}
  2. ( 1 P ) = 1 {\displaystyle \left({\frac {1}{P}}\right)=1}
  3. ( a b P ) = ( a P ) ( b P ) {\displaystyle {\bigg (}{\frac {ab}{P}}{\bigg )}={\bigg (}{\frac {a}{P}}{\bigg )}{\bigg (}{\frac {b}{P}}{\bigg )}}
  4. Első kiegészítési tétel:[1]
    ( − 1 P ) = ( − 1 ) P − 1 2 {\displaystyle {\bigg (}{\frac {-1}{P}}{\bigg )}=(-1)^{\frac {P-1}{2}}}
  5. Második kiegészítési tétel:[2]
    ( 2 P ) = ( − 1 ) P 2 − 1 8 {\displaystyle \left({\frac {2}{P}}\right)=(-1)^{\frac {P^{2}-1}{8}}}
  6. Reciprocitási tétel:[3] ha P és Q relatív prím páratlan számok, akkor
    ( P Q ) = ( Q P ) ( − 1 ) ( P − 1 ) ( Q − 1 ) 4 {\displaystyle {\bigg (}{\frac {P}{Q}}{\bigg )}={\bigg (}{\frac {Q}{P}}{\bigg )}(-1)^{\frac {(P-1)(Q-1)}{4}}}
  7. Ha ( a P ) = − 1 {\displaystyle {\bigg (}{\frac {a}{P}}{\bigg )}=-1} , akkor a kvadratikus nemmaradék moduló P.[4]

Ha viszont ( a P ) = 1 {\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

( 2 15 ) = ( 2 3 ) ⋅ ( 2 5 ) = ( − 1 ) ⋅ ( − 1 ) = 1 {\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 ( a P ) {\displaystyle \left({\frac {a}{P}}\right)} Jacobi-szimbólum értékeit tartalmazza 3 ≤ P ≤ 17 {\displaystyle 3\leq P\leq 17} és 0 ≤ a ≤ 16 {\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 ( a , P ) {\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.

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

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

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

( a P ) ≡ a P − 1 2 ( mod P ) {\displaystyle \left({\frac {a}{P}}\right)\equiv a^{\frac {P-1}{2}}{\pmod {P}}} ,

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 2 ≤ a < P {\displaystyle 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 {\displaystyle 2^{-k}} .[6]

Jegyzetek

  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

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