Kedves Tamás,
A tisztán szoftveres megoldások egy kis kiinduló adatból gyártanak hosszú sorozatot. Mondjuk egy 64 (vagy n) bites kezdőértékből készítenek 1024 (N) hosszú bitsorozatot. Mivel kezdőértékből kevesebb van, mint N-hosszú sorozatból, a lehetséges sorozatoknak csak kis töredékét állíthatják elő. A véletlenszám-generátor tehát az összes sorozatnak egy kis részhalmazából, 2n sorozat közül választ véletlenszerűen.
A különböző hardver-zajok hozzákeverése ezen segít, és ez bizonyos esetekben szükséges is.
* * *
Sokféle véletlentesztet lehet készíteni. A [3]-beli példában az is működött, hogy ellenőriztük az eloszlást. De azt is figyelni lehet, hogy különböző minták (pl. töbször egymás után ugyanaz az érték) milyen gyakran fordulnak elő.
Jó játék az a program, ami tippel, hogy fejet vagy írást fogsz mondani. Te mindig megnyomod az I vagy az F gombot, a gép ezután megmondja, hogy mire tippelt, és eddig hányszor talált és hányszor tévedett.
A program úgy működik, hogy nyilvántartást vezet a szokásaidról, hogy az utolsó egy-két lépés után mit szoktál mondani. Például, ha te kétszer egymás után fejet mondtál, és a program mindkétszer eltalálta, akkor mit szoktál mondani gyakrabban.
* * *
Az elméleti megközelítés valami ilyesmi. Egy "véletlenteszt" egy olyan program, ami minden sorozatra mond valamit, mondjuk azt hogy A vagy azt, hogy B. A teszttől elvárjuk, hogy "gyors" legyen, mondjuk létezzen egy olyan c konstans, hogy egy N hosszú sorozathoz tartozó választ legfeljebb Nc lépésben kiszámolja.
Képzeljük el, hogy a tesztet kipróbáljuk N hosszúságú álvéletlen sorozatokon, amiket egy véletlenszám-generátorral állítunk elő, és kipróbáljuk igazi véletlen sorozatokon is. Mindkét esetben bizonyos sorozatokra A-t, a többire B-t fog mondani. Ha a két válasz eloszlása lényegesen különböző a véletlen és az álvéletlen sorozatokon, akkor a teszt lebuktatja a véletlenszám-generátort.
Az, hogy az eloszlások lényegesen különbözők, azt jelenti, hogy van olyan c2 konstans, hogy az A válasz valószínűségének különbsége legalább 1/Nc2.
Legyen mondjuk a sorozat hossza is n hatványa, Nnc3 és a véletlenszám-generátortól is elvárjuk, hogy az N hosszú sorozatot legfeljebb Nc4 lépésben előállítsa.
A kérdés ezek után az, hogy van-e olyan véletlenszám-generátor, ami minden tesztet átver. Bizonyos számelméleti sejtéseket feltételezve, ilyen konstrukciók léteznek. Például ha feltételezzük, hogy egy n-jegyű számot nem lehet n-hatvány idő alatt prímtényezőkre bontani, akkor ebből lehet jó (bár kicsit lassú) véletlenszám-generátort konstruálni.
|