Lovász László

2. Primtesztelés és -faktorizáció

Egy pozitív egész számot prímszámnak nevezünk, ha 1-en és önmagán kívül más egész számmal nem osztható. Az 1-et nem tekintjük prímnek, de utána aztán sok példát látunk: 2, 3, 5, 7, 11, 13 stb. Azokat a természetes számokat, melyek nem prímek, fel lehet bontani prímszámok szorzatára, például 6=2*3, 40=2*2*2*5 stb. - ezt a felbontást nevezzük prímfaktorizációnak.

A prímszámokkal kapcsolatban két fontos algoritmikus problémát fogalmazhatunk meg: ha adott egy k jegyű szám, hogyan tudjuk eldönteni róla, hogy prímszám-e; és ha nem prímszám, hogyan tudjuk megtalálni a prímtényezőit?

Mindkét kérdésre könnyű ,"véges" választ adni: csak ki kell próbálni, hogy osztható-e a szám 2-vel, 3-mal, 4-gyel, 5-tel stb. Ha találunk olyan számot, amelyik osztója, akkor tudjuk, hogy nem prímszám, és a felbontást is könnyű megcsinálni. A baj ezzel az, hogy iszonyú sok számot kell kiprobálni: ahhoz, hogy egy 100 jegyű számról eldöntsük, hogy prím-e, 10¹⁰⁰ számot kell kipróbálni, ami nagyobb, mint a világegyetem bármilyen paramétere. Kis ravaszsággal észrevehetjük, hogy elegendő a szám négyzetgyökéig kipróbálni a számokat. De ez sem segít eleget: egy 100 jegyű szám négyzetgyöke 50 jegyű, és 10⁵⁰ is messze túl van a lehetőségek határán.

Kiderül, hogy az első kérdés sokkal könnyebb, mint a második: olyan hatékony (polinomiális) algoritmusok vannak, amelyek akár 1000 jegyű számról is könnyedén eldöntik, hogy prím-e. A tényezőkre bontásra azonban csak olyan algoritmus ismert, amely lényegében exponenciális: 100-nál több jegy esetén már csak nagy üggyel-bajjal működnek, 150 jegy fölött pedig egyáltalában nem. Látni fogjuk, hogy ennek az egyszerű ténynek hallatlan gyakorlati következményei vannak.

Hogyan lehetséges, hogy a prímfaktorizáció ennyivel nehezebb, mint a prímtesztelés? Azt gondolnánk, hogy mindegyikhez végig kell próbálni az adott számnál kisebb számokat, hogy nem osztható-e velük az adott szám. Nyilvánvaló, hogy ez nagyon hosszadalmas lenne, ezért valahogy másképp kell eljárnunk. A hatékony prímtesztelő algoritmusok az ún. "kis" Fermat-tételen alapulnak (a "kis" jelző nem a tétel fontosságára utal, hanem azért használjuk, hogy megkülönböztessük a csak nemrégen bebizonyított "nagy" Fermat-tételtől. Fermat, a nagy 17. századi francia matematikus csak az előbbinek a bizonyítását adta meg.)

Fermat tétele szerint, ha p prímszám, és a tetszőleges egész szám, akkor

p | a^p-a

(p osztója az a^p-a számnak). Például, 2⁵-2=30 osztható 5-tel. Ha egy p számról el akarjuk dönteni, hogy prímszám-e, akkor megnézzük, hogy 2^p-2, 3^p-3 stb. oszthatók-e p-vel. Ellentétben a fenti egyszerű teszttel, ezt nem kell nagyon sok számra kipróbálni, elegendő csak néhányra.

(Sok mindent söpörtem itt a szőnyeg alá: néhány p számra ez a módszer hamis pozitív eredményt ad, ezért kicsit módosítani kell; nagy számok nagyon nagy hatványaival kell számolni, ami megoldható, de nem nyilvánvaló, hogyan stb. De mindezeket megoldva ez a teszt, melyet Miller-Rabin-tesztnek hívnak, mint láttuk, nagyon jól működik.)