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. |