Pszeudo-véletlenszám generátor

(zene) (levélsusogás) Amikor megfigyeljük a fizikai világot, akkor mindenütt véletlenszerű ingadozást tapasztalunk. Valódi véletlenszerű számokat generálhatunk, ha megmérjük a zajnak is nevezett véletlenszerű ingadozást. Amikor a zajt mérjük, – ezt mintavételnek hívják – egy számsorozatot kapunk. Egy, kettő, három. négy... Például, ha megmérjük az idő függvényében a TV elektromos áramának statikus zaját, akkor igazi véletlen sorozatot kapunk. Megjeleníthetjük ezt a véletlen sorozatot úgy, hogy rajzolunk egy olyan útvonalat, ami a számok alapján változtat irányt: ezt véletlen sétának hívjuk. Figyeld meg, hogy semmilyen szinten se találsz mintázatot. A sorozat bármely pontján a következő lépés megjósolhatatlan. A véletlen folyamatokat nem-determinisztikusnak hívják, mivel nem lehet azokat előre jelezni. A gépek viszont determinisztikusak. Működésük megjósolható és megismételhető. 1946-ban Neumann János katonai számításokat végzett a hidrogénbomba tervezése során. Az ENIAC számítógép segítségével ismételten ki akarta számolni az atomfúzió során végbemenő folyamatokat. Ehhez arra volt szükség, hogy gyorsan generálhassák véletlenszámok sorozatát, amit szükség esetén meg is lehetett ismételni. Viszont az ENIAC-nak kevés belső memóriája volt, nem volt mód hosszú véletlenszám sorozatok tárolására. Ezért Neumann kidolgozott egy algoritmust, amivel mechanikusan szimulálni tudta a véletlenszerűséget a következőképpen: Először választott egy valódi véletlenszámot, amit „magnak” hívnak. Ez a szám származhat egy zaj mérésből, vagy a pillanatnyi időből milliszekundumokban. Majd ezt a magot felhasználják egy egyszerű számításban. Szorozd meg a magot önmagával, majd vedd ki az eredmény közepét. Ezt használd fel a következő lépésben magnak. Annyiszor ismétled meg a folyamatot, ahányszor szükséges. Ez négyzet-közép módszerként ismert, és az első a pszeudo-véletlenszám generátorok hosszú listáján. A sorozat véletlenszerűsége csak a kezdeti mag véletlenszerűségétől függ. Ugyanaz a mag, ugyanaz a szekvencia. Mi a különbség a véletlenszerűen generált és a pszeudo-véletlenszerűen generált számsorozat között? Ábrázoljuk mindkét sorozatot véletlen sétával. Hasonlóan alakulnak, amíg fel nem gyorsítjuk az eseményeket. A pszeudo-véletlen sorozat előbb-utóbb ismétlődni fog. Ez akkor következik be, amikor az algoritmus egy, már korábban használt maghoz ér, ekkor a ciklus ismétlődni fog. A pszeudo-véletlen sorozat ismétlésmentes hosszát „periódusnak” hívják. Ezt a periódust a kiinduló mag mérete szigorúan korlátozza. Például ha kétszámjegyű magot használunk, akkor az algoritmus maximum 100 számot képes generálni, mielőtt újra előjön a mag és a ciklus megismétlődik. Háromjegyű mag nem tud 1000 számnál többet ismétlődés nélkül létrehozni. Négy számjegy esetén nem haladhatja meg a 10 000-et ismétlődés nélkül. Ha elég nagy magot választunk, akkor a sorozat akár több billió is lehet ismétlődés nélkül. De fontos a fő különbség. Ha pszeudo-véletlenszámokat generálsz, számtalan sorozat nem fordulhat elő. Ha Alíz egy 20 elemű igazi véletlen eltolást generál, az az összes lehetséges eltolások halmazából egyenlő valószínűségű választást jelent. Ez a halmaz 26 a 20-adikon elemet tartalmaz, ami csillagászati méretű. Ha az aljában állva felvilágítanánk, a tetején lévő szemlélő kb. 200 000 000 évig nem látná meg a fényt. Vesd ezt össze azzal, amikor Alíz egy 20 jegyű pszeudo-véletlenszámot generál négyjegyű maggal. Ez megegyezik 10 000 lehetséges kezdeti magból való véletlenszerű választással, ami azt jelenti, hogy csak 10 000 különböző sorozatot tud generálni, ami elenyésző mennyiség az összes lehetséges sorozathoz képest. Amikor a véletlenszerű helyett a pszeudo-véletlent választjuk, akkor a kulcs-teret leszűkítjük egy lényegesen kisebb mag-térre. Ahhoz, hogy a pszeudo-véletlen sorozat megkülönböztethetetlen legyen a véletlenszerűen generált sorozattól, az kell, hogy számítógéppel se lehessen értelmesen az összes mag kipróbálásával megkeresni a megoldást. Ez egy fontos megkülönböztetést jelent a számítástudományban a tekintetben, hogy mi lehetséges, illetve mi lehetséges belátható időn belül. Ugyanezt a logikát használjuk, amikor biciklizárat veszünk. Tudjuk, hogy bárki végigpróbálhatja az összes lehetséges kombinációt, amíg rá nem talál a megoldásra. De ez több napba kerülhet. Úgyhogy azt mondjuk, nyolc óráig biztonságban vagyunk. Pszeudo-véletlen generátorok esetén a biztonság a mag hosszúságával növekszik. Ha a legerősebb számítógépnek több száz évre volna szüksége az összes magot végigpróbálni, akkor jogosan feltételezhetjük, hogy gyakorlatilag biztonságos, bár nem jelent tökéletes biztonságot. Ahogy a számítógépek sebessége nő, a mag méretének is nőnie kell. Pszeudo-véletlenszerűséggel Alíznak és Bobnak nem kell megosztani előre a véletlen eltolási listájukat. Elég a rövidebb véletlen magot megosztani, amiből szükség esetén elő tudják állítani ugyanazt a véletlenszerű sorozatot. De mi van akkor, ha soha nem találkoznak, hogy megoszthassák a magot?