Faktorizáció, prímszámprobléma és evolúció

Már Eratosztenesz óta ismernek olyan eljárásokat, amelyek egy adott n szám prím voltát eldöntik és ha a szám nem prím, akkor szorzótényezôkre bontják. Ezek az eljárások azonban -- beleértve olyanokat is, mint az Eratosztenesz szitája, vagy a próbaosztás -- nagyon idôigényesek. "Kis" számoknál ugyan ez nem játszik nagy szerepet, nagyobb számok esetén azonban hamar elérjük a kivitelezhetôség határát. Ezt egy példával fogjuk késôbb érthetôbbé tenni.

Jobb és gyorsabb eljárásokra van ezért szükség. Itt sincs módunk most a fejlôdést nyomon követni, csupán a már jelzett példára utalunk az elôadás végén. De elôbb a dolog két másik vonatkozását szeretném érinteni.

A leggyorsabb faktorizáló eljárások alkalmazása is hamar - még a legnagyobb számítógépek igénybevétele esetén is - korlátokba ütközik. Így például jelenleg egy körülbelül 150 jegyû szám faktorizálása - kedvezôtlen esetben - nagyjából 30 évnyi gépidôt igényelne.

Ezt a tényt használják ki új titkosítási eljárások, mint például a Rivest, Shamir és Adleman [9] által kidolgozott és a nevük után RSA-eljárásnak nevezett módszer. Egy digitális üzenet rejtjelezése moduláris szorzásokkal történik valamilyen adott n modulus szerint, amely két prím, p és q szorzata. Ez a feladat igen gyorsan elintézhetô. Egy potenciális kódfeltörônek, aki egy ilyenformán kódolt üzenet tartalmát szeretné megismerni, minden adat (még az n szám is) rendelkezésére áll. Mégis kudarcra van ítélve az idô gondok miatt, mivel a dekódoláshoz az n=pq felbontás ismerete szükséges.

A prímszámprobléma esetében sem ismert még elméletileg is igazolt praktikus gyors algoritmus, aholis a "gyors" jelzô azt jelentené, hogy adott n szám esetén a számolási idô, azaz a szükséges számolási lépések vagy idôegységek száma nem haladja meg log n egy rögzített hatványának konstansszorosát. Ekkor úgynevezett polinomiális algoritmusról beszélünk. Mégis, hirtelen megváltozik a helyzet, ha lemondunk a teljes bizonyosságról.

Mert 1976-ban M.O. Rabin [8] talált egy polinomiális algoritmust, amelyik nagyon nagy valószínûséggel eldönti egy számról, hogy prím-e.