Nagy prímek előállítása

Prím számokat másképp is elő lehet állítani, például Mersenne prímeket, amelyek 2^n-1 alakúak, ezek azonban kevesen vannak, és ha ilyen prímet használunk, akkor egyszerű próbálgatással gyorsan fel lehet törni a rejtjelezést.

Hogyan tudjuk eldönteni egy nagy számról, hogy prím-e? A válasz az, hogy teljes biztonsággal sehogy. Erre ugyanis csak egy módszer van: az, hogy végignézzük 1 és a szám négyzetgyöke közötti egészek mindegyikét, hogy osztója-e valamelyik a számnak. Ha egyik sem osztója, akkor a szám prím, ellenkező esetben az első osztó megtalálásakor abbahagyhatjuk a keresést, mert a szám nem prím. Ezt azonban nem tudjuk megtenni, hiszen pont olyan nagy prímet szeretnénk találni, amelyikkel ez már nem tehető meg belátható időn belül.

Ugyanakkor a jó hír az, hogy tetszőleges biztonsággal meg tudjuk mondani, hogy egy p szám prím-e, vagy sem. Ha a szám prím, akkor igaz rá a Fermat tétel. Ha viszont nem prím egy szám, akkor jó esélyünk van rá, hogy találunk olyan a egész számot, amely kisebb, mint p, és p nem osztója a^p-1-1-nek. Mivel p elég nagy meglehetősen sok a egész áll rendelkezésünkre a teszteléshez. A gyakorlat azt mutatja, hogy ha p nem prím, akkor p az esetek felében nem osztója a^p-1-1-nek. Ez pedig azt jelenti, hogy 100 sikeres teszt esetén annak a valószínűsége, hogy a szám mégsem prím 2^-100*100%. Az ilyen valószínűségű eseményekre a köznapi életben nem azt szoktuk mondani, hogy nem valószínű, hanem azt, hogy lehetetlen.

Egy ilyen tesztelés persze nagyon nagy számítási kapacitást igényel, hiszen egy valamilyen a számhoz ki kell számítani a^p-1-1 illetve ami ezzel ekvivalens a^p-1-nek p-vel adott osztási maradékát. p pedig nagyságrendileg 64...128 bájtos bináris egész szám, ami azt lejenti, hogy decimális alakban több, mint 130 jegyű, és ez van a kitevőben!

A gyakorlat során egy tesztelés, azaz egy modulo hatványozás 486, 66MHz gépen másodperc nagyságrendbe esik. Mivel sok nem prímet találunk gyorsítani lehet az algoritmust azzal, ha például a páros számokat nem vizsgáljuk. Ezzel kétszeresére nő a sebesség. További gyorsítási lehetőség ha kihagyjuk a 3-mal, 5-tel sb. osztható számokat. Általánosabban megfogalmazva, mielőtt a kemény, és számításigényes Fermat tételen alapuló tesztelést elkezdjük megvizsgáljuk, hogy a szám osztható e valamilyen 2 és előre rögzített n közötti prímmel.

Természetesen nem minden prím rendelkezik olyan jó tulajdonsággal, mint a 2, hogy egy akárhány jegyű szám bináris ábrázolásánál elegendő az utolsó bitet megvizsgálni annak eldöntésére, hogy osztható-e a szám kettővel. Az 3-mal, 5-tel, 7-tel stb. való oszthatóság eldöntéséhez maradékot kell képezni, ami szintén nem túl gyors folyamat. Ha azonban egy tömbben tároljuk a kis, például száznál kisebb prímeket, mindegyiket a példa kedvéért 16 biten, és egy másik, ugyanennyi elemet tartalmazó tömbbe eltesszük a tesztelt p szám megfelelő prímmel való osztási maradékait, akkor p+j maradékainak megállapításához elegendő a már kiszámított maradék plusz j maradékát kiszámolni, ami abban az eseteben, ha j is 16 bites szám csak 16 bites aritmetikát igényel.

Ez azt jelenti, hogy az első, véletlenszerűen előállított p szám után nem egy véletlenszerűen előállított következőt vizsgálunk meg, hanem az eggyel nagyobbat, vagy kisebbet, és így a j értéke +-1,2,3,...65535 lehet. Ha ebben a tartományban nem találunk prímet, aminek egyébként a gyakorlat szerint igen kicsi a valószínűsége, akkor előállíthatunk egy újabb véletlen p értéket.