Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

2. Véletlenszámok generálása

2. Véletlenszámok generálása

A következőkben véletlenszámok generálásával fogunk foglalkozni. Ezek az általunk készített számok valójában „ ál-véletlenszámok”, hiszen egy meghatározott szabály szerint képezzük őket egy adott véletlen kezdőértékből, a „ magból”. (Ezt általában a számítógép órája alapján képzik). Lehetne „igazi” véletlen számokat is generálni a radioaktív bomlást vagy a kvantumfizika egyéb jelenségeit használva, de ezek nem volnának kellően hatékonyak.

A véletlenszámokat általában 2-es számrendszerben adjuk meg, és tegyük fel pl., hogy 8 számjegyből állnak (mivel főleg a számítástechnika alkalmazza őket). Mikor jó egy véletlenszám-generátor? Könnyebb azt definiálni, hogy mikor rossz: akkor mondjuk, hogy feltörhető, ha elegendő tag (mondjuk az első n ) ismeretében valaki hatékony számolással meg tudja mondani vagy legalábbis tippelni, hogy mi lesz a sorozat következő tagja.

Ahhoz, hogy ezt pontossá tegyük, a számítási bonyolultság fogalmára van szükség. Ezt csak egy példán világítjuk meg. Tekintsük az x = 0110 10 természetes számot, ahol x jegyeinek száma n . x 2 kiszámításához kb. n 2 db műveletet kell elvégeznünk. Ezzel szemben x prímfelbontásának a meghatározásához, a legegyszerűbb módszerrel, legalább x ? 2 n / 2 osztást, és a ma ismert leghatékonyabb módszerrel is majdnem ennyit. Mivel n 2 //<// 2 n / 2 , ha n elég nagy, x 2 kiszámításának számítási bonyolultsága kisebb, mint x prímekre bontásának. Ha egy függvény elég nagy n esetén kisebb, mint n egy hatványa (a kitevő lehet 2, 3 vagy akár 100), akkor polinomiálisnak nevezzük, míg a 2 n / 2 függvényt exponenciálisnak. (Ha valaki utánaszámol, akkor azt fogja találni, hogy nagyon sok n értékre n 10 nagyobb, mint 2 n . Ebben a matematikai vizsgálatban azonban a nagyon nagy n értékek érdekelnek minket. 2 n gyorsabban nő, mint n 10 , vagy akár n 100 , és előbb-utóbb minden hatványfüggvénynél nagyobb lesz.)

Mit jelent az, hogy hatékonyan? Azt, hogy ehhez elég sok, pl. n 10 időt adunk (polinomiális időt); de nem túl sokat, pl. nem 2 n -et (tehát nem exponenciálisat).

Mit jelent az, hogy tippelni? Ha valaki fel akarja törni a generátorunkat, akkor 1 / 2 esélye biztos van rá, hogy eltalálja a következő jegyet (a korábbi jegyektől teljesen függetlenül, pénzfeldobással tippelhet). Azt akarjuk, hogy ennél sokkal nagyobb esélye ne is legyen: ha az esélye 1 2 + 1 n 2 , vagy akár 1 2 + 1 n 10 , azt már nem engedjük meg. A „jó” generátornak tehát olyannak kell lenni, hogy ezt polinomiális idő alatt senki se tudja megtenni.

Azt, hogy egy generátor megbízható-e ebben az értelemben, egyáltalában nem könnyű ellenőrizni. Az egyik első képzési módot Neumann János adta meg: legyen pl. a mag x 1 = 10101001 , képezzük ennek a négyzetét, és vegyük ki a középső 8 számjegyet, ez lesz x 2 , majd hasonlóan folytassuk az eljárást x 2 -vel és így tovább. Ez a módszer azonban nem volt jó, mivel viszonylag könnyen fel lehetett törni (sok esetben nagyon hamar periodikussá vált a sorozat). Egy másik módszer a 2 , vagy általánosabban x (ahol az x mag egy viszonylag kicsi pozitív egész szám) számjegyeinek a felhasználása, ami ugyan soha nem lesz periodikus, de más okokból ugyancsak nem volt megfelelő. A gyakorlatban legtöbbet használt generátor a következőképpen működik: legyen x a mag, A , B , illetve N pozitív egészek, és x i = ( A x i - 1 + B ) mod N . Ez az eljárás könnyen programozható, gyors, és általában jó eredményt ad, de a fenti szigorú elméleti követelményeknek nem felel meg (vagyis feltörhető).

Annál meglepőbb, hogy van ilyen értelemben „jó” véletlenszám-generátor is. Ehhez be kell vezetnünk egy fogalmat: Legyen f ( N N ) egy-egyértelmű függvény! f -et egyirányú függvénynek nevezzük, ha f hatékonyan kiszámítható, de f - 1 nem. A Goldreich–Levin féle generátor egy ilyen egyirányú függvényt használ. A mag álljon 2 db n / 2 jegyű szám egymás után írásából, ezek legyenek x és y . x jegyei rendre x 1 , x 2 , …, x n / 2 és y jegyei rendre y 1 , y 2 , …, y n / 2 . Legyen továbbá f egyirányú függvény! Bevezetünk egy műveletet: x ? y = x 1 y 1 + x 2 y 2 + + x n / 2 y n / 2 . Az első véletlenszámunk legyen x ? y , a második f ( x ) ? y , a harmadik f ( f ( x ) ) ? y és így tovább! Be lehet bizonyítani, hogy ezt a sorozatot nem lehet föltörni.

Az előbb azt mondtuk, hogy egy n -jegyű x természetes szám prímfelbontásához mintegy 2 2 n / 2 művelet szükséges, ami exponenciálisan sok. Ha csak arra vagyunk kíváncsiak, hogy x prímszám-e, akkor a kérdést el lehet dönteni polinomiálisan is, kb. x 3 művelet elvégzésével. x prímfelbontásának megkereséséhez azonban a legravaszabb módszerrel is több, mint 2 n műveletet kell elvégeznünk, ami exponenciális függvény, így nagy n -ekre nem számítható ki megfelelően rövid idő esetén. Ezt a tényt használja ki a kriptográfia (a titkosírások tudománya) is. A jelenleg legelterjedtebb titkosírási módszer (RSA-eljárás) is ezen alapul, és ha sikerülne kb. 200–300 jegyű számok prímfelbontását viszonylag rövid idő alatt (legfeljebb 1 év) megtalálni, akkor ez egy hatalmas gazdasági lavina elindulását jelentené. Ha a maffia által foglalkoztatott matematikus(ok) jönnének rá a probléma megoldására, akkor a bankok széfjei egy csapásra kiürülnének, az FBI és a Pentagon titkos adatai ismertté válnának, a folyószámlák lenullázódnának, vagy éppen hatalmas adósságok gyűlnének fel rajtuk. Így érthetővé válik, hogy ma miért foglalkozik ezzel a problémával sok matematikus – egyik részük a bankok foglalkoztatásában. Emellett a kriptográfusok között is viták vannak. Sajnos olyan titkosírási rendszer, amelynek a megfejthetetlensége matematikai egzaktsággal be is van bizonyítva, nincsen. Alkalmazzunk-e új, de még kipróbálatlan rendszereket, amelyekről a kidolgozójuk úgy érzi, hogy feltörhetetlenek, de ez talán csak azért nincsenek feltörve, mert kevesen próbálkoztak vele – vagy használjuk csak az évtizedek óta megszokott titkosírási rendszereket, amelyeknél jóval kisebb esélyben áll fenn a megfejtés lehetősége, de ha mégis feltöri őket valaki, akkor egyszerre omlik össze minden? Nincs jó válasz erre a kérdésre.

Az internetes kapcsolatokban mindössze 50-jegyű kódokat használnak, ezek prímtényezős felbontása pedig egyre inkább lehetővé válik, éppen az internet segítségével. Ezzel a módszerrel például már sikerült A. Lenstra-nak megadni egy 140-jegyű szám prímtényezős felbontását, amelyet az 1970-es években tűztek ki Rivest, Shamir és Adleman (az RSA rendszer névadói); megoldását a kitűzők 2050-nél későbbre jósolták.

Lenstra olyan egyszerű módszert használt, amit egy középiskolai előadás keretében is vázolni lehet. Legyen az egyszerűség kedvéért N = p · q , ahol p és q prímszámok! N -et ismerjük, de p -t és q -t nem. Hogy reálisan lássuk a számítási nehézséget, legyen N mondjuk 50-jegyű szám.

Az első gondolat az, hogy két olyan négyzetszámot keresünk, amelyek különbsége N -nel osztható. Ha N | x 2 - y 2 = ( x - y ) ( x + y ) , de N egyik tényezőnek sem osztója, akkor nyert ügyünk van: legyen mondjuk p | x - y és q | x + y , így nyilván ( N , x - y ) = p . Két szám legnagyobb közös osztóját pedig már könnyen meghatározhatjuk az euklideszi algoritmus segítségével, így meg tudjuk adni p -t és így N prímtényezős felbontását is.

A fő nehézség az, hogy ilyen x -et és y -t találjunk. A trükk az, hogy olyan számokat keresünk, amelyek „közel” vannak N egy többszöröséhez (csak „kicsit” nagyobbak), és csak „kis” prímekből állnak (mondjuk, az első 10 10 prímből). Legyen u ilyen szám, és v = u mod N . Ekkor v viszonylag kicsi, és így v is csak „kis” prímekből áll. Így ezek prímtényezős felbontását meg tudjuk adni:

u = 2 a 3 b 5 c , v = 2 a ' 3 b ' 5 c ' .

Tudjuk azt is, hogy u - v osztható N -nel. Ha az a , b , c , …, a ' , b ' , c ' , … kitevők mindegyike páros volna, akkor készen is volnánk, de hát persze ilyen szerencsére nem lehet számítani.

A megoldás az, hogy keressünk sok ilyen ( u , v ) párt. Megmutatható, hogy ha több párt találunk, mint 10 10 (ahány „kis” prímet használunk), akkor ezekből kiválasztható (éspedig hatékonyan) valahány a következő tulajdonsággal: ha a megfelelő u -k szorzata U , a megfelelő v -k szorzata V , akkor x 2 = U ( U , V ) és y 2 = V ( U , V ) négyzetszámok, és a különbségük osztható N -nel. Kis szerencsével x - y és x + y nem lesz N -nel osztható. Amint láttuk, ebből már az N prímfelbontása meghatározható.

Az internet segítsége ott van, hogy a fenti ( u , v ) párokat sok-sok résztvevő sok-sok gépen egymástól függetlenül keresheti, és ha talál ilyet, jelenti a központnak. Semmi egyéb szervezésre, adatok cseréjére, részletszámítások összehangolására nincs szükség.