Egy random szám generálása a processzor órajeléből történik?

Többféle módon lehet véletlent generálni. Vannak hardveres megoldások, de a legtöbb esetbe ez szoftveresen történik. Ez is történhet az operációs rendszer szintjén – pl. Linux esetén ezt használják –, illetve az adott program szintjén is.

Az ANSI C véletlenszám generátora így néz ki:

x[n+1] = a * x[n] + c (modulo m)

Ahol:

x[0] = 123 456 789

a = 1 103 515 245

c = 12345

m = 2³¹ = 2 147 483 648

(Más programnyelvekben is gyakran használják ezt az algoritmust, csak esetleg más konstansokkal. Lásd: [link] )

Ez egy 31 bites véletlenszámot fog generálni, azaz egy 0 és 2³¹-1 közötti számot. Ha ennél kisebb intervallumban kell generálni számot, akkor egyszerűen csak osztani kell.

A konstansok megválasztása nem lényegtelen. (Van egy csomó feltétel, lásd a belinkelt Wikipedia oldalt.) Jól megválasztott konstansok esetén a generátor csak 2³¹ generálás után ismétli önmagát, és minden számot csak egyszer generál le. Illetve a kisebb intervallumban generált számok eloszlása, szórása kvázi megegyezik a valódi véletlenével.

Hogy a program ne mindig ugyanazt a véletlen számsort dobja minden egyes indításnál, ezért szokás a kezdőértéket mondjuk a pontos időből származtatni. De adott esetben egy IP címmel, vagy egy MAC címmel is meg lehet fűszerezni ezt az inicializálást.

Linux esetén az egymással párhuzamosan futó programok is adnak egy csavart a történetbe, mert lehet, hogy a generátor ismétli önmagát, de két generálás között más programok is lekérnek akár egy tucatnyi véletlen számot, így az adott program által kapott véletlen számok nagyban függnek attól is, hogy milyen egyéb programok futnak, amik még véletlen számokat kérnek le, és azok éppen mit csinálnak.

De vannak ennél cizelláltabb megoldások is. Pl. a Mersenne Twister algoritmus sokkal összetettebb, de cserébe 32 bites egészeket ad, és kb. 2¹⁹⁹³⁷-1 véletlenszám generálása után kezdi ismételni önmagát. Lásd: [link]

~ ~ ~

Mint említettem vannak hardveres megoldások, van, ami két rádióaktív bomlás közötti időből generál véletlent. Ennél egyszerűbb egy zajdióda, ami kvázi az elektromos zajból generál egy 1 bites véletlent.

> Ha ismerjük a peremfeltételeket, akkor ez a szám is ismert?

Nem tudom mit értesz pontosan peremfeltétel alatt, de igen, ha ismered a véletlenszám-generátor kezdőértékét, akkor ismert lesz az általa generált számsor is.

Hardveres megoldás esetén viszont aligha fogod ismerni mindezt, mert kvantummechanikai okokból ismeretlen lesz számodra azoknak a paramétereknek az összessége, ami befolyásolja a generált számot.

Nos, amit az előző kolléga írt, teljesen igaz, de fontos kiegészítenem egy két dologgal:

A véletlenszerű véletlenszám generálás során ( számok húzása és visszadobása, majd újboli húzás) a korábbinál lényegesen nagyobb eséllyel biztosítja az ismétlődő számokat. Ez nagy fogyatékossága a véletlenszám generáló eljárásoknak.

A "hagyományos" véletlengenerátorok kezdeti feltételeit ismerve , vagyis hogy hol tart benne az a buffer ami a számot ábrázolja, ismert és deerminisztikus a véletlenszám.

A több szálon futó, linuxos véletlenszám generálás lényegesen jobb eredményt ad, de itt is elmondható, hogy gyan ki nem lehet találni a következő számot, de az igaz véletlenszerű eloszlást csak közelítik.

Emlékeim szerint használtak véletlenszám generálásra nagy prímszámok számjegyeiből vett szakaszos mintákat is, azon alapszik, hogy nincs rá determinisztikus képlet, és könnyű prímeket keresni.

Hamarabb akartam írni, de nem volt rá időm.

Viszont ami kapásból a szememet szúrta:

"Ez egy 31 bites véletlenszámot fog generálni, azaz egy 0 és 2³¹-1 közötti számot. Ha ennél kisebb intervallumban kell generálni számot, akkor egyszerűen csak osztani kell."

Tegyük fel, hogy követi az egyenletes eloszlást a generátor. Ha a kapott számot elkezded egyszerűen csak osztani, mert kisebb intervallumra van szükséged, akkor garantáltan "torzítani" fogja az egyenletes eloszlást azaz valamilyen számokat "szívesebben" generál mint másokat. Ugyanis ad egy egész számot a generátor mely az osztandó, az osztót úgy választjuk meg, hogy a maximális 2^31-1 esetében a hányados legyen a kívánt max érték, a maradékot egyszerűen csak eldobjuk, márpedig mindig lesz maradék mivel a 2^31-1 prím. Több osztandó esetében jön ki ugyanaz a hányados. Nem lesz igazságos hogy mely osztandókra jön ki ugyanaz a hányados, mivel lesz olyan hányados mely több osztandóból kijöhet és lesz mely kevesebből.

Legegyszerűbben úgy lehet kisebb intervallumot csinálni belőle, hogy ami az intervallumon kívül esik azt nem vesszük figyelembe. Ez viszont csak elméleti megoldásnak jó, mivel túl lassú, pazarló. (Feltéve ha eredetileg a generátor követi az egyenletes eloszlást.) Régebben csináltam erre az ötletre alapuló random osztályt c++ - ban, de okosabban csináltam mint az alapötlet, linux op rendszerbe épített generátorra alapult.

"Linux esetén az egymással párhuzamosan futó programok is adnak egy csavart a történetbe ..."

Linux esetében operációs rendszer szinten 2 fajta generátor van mely ugyanazon alapul csak egy lényeges különbség van közöttük. Legkevesebb egy bájt random-ot lehet kérni a rendszertől, egyébként meg adott pufferméretnyi random bájtot egy rendszerhívással.

Az egyik módszer szerint van egy kezdőállapot mely lehet a rendszeridő, a linuxos generátor beleveszi a processzor hőmérsékletet a felhasználó által lenyomott bellinyűleütéseket, az egérmozdulatokat stb. A kezdőállapot ot numerikus értéké alakítja. Van a "fazék" mely a random pool a kezdőállapotból indul, kever rajta egyet majd "merít" belőle megkapod a random értéket majd megint kever rajta. Ez linux esetében a /dev/urandom (Pseudo Random = álvéletlen).

A másik módszer szeint ugyanígy "főzzük" a random-ot, de a "kondérból" csak akkor "merhetünk" random-ot, ha a összegyűlt a rendszerben annyi bitnyi entrópia mint amennyit "merni" akarunk pl a hálózati forgalom csomagjaiban lévő késletetés mikro secundumban, a billenyűk közötti leütések szintén nagyon pontosan mérve stb stb (a rendszernek rengeteg paraméterét beleveszi). Ez a linux /dev/random megfelelője.

Vagyis az egyik módszer szerint akkor generál tovább ha van hozzá elég entrópia, ez biztosítja a (true random-ot) a valódi randomot. Az kell hozzá, hogy általunk nem pontosan befolyásolható tényezőktől függ, melyre olyan függvényt illeszt melyre teljesül a lavinaeffektus. Vagyis bármely bemenetnek egyetlen bitjének megváltoztatása esetén a kimenetnek bármely bitje 50% valószínűséggel megváltozik. Ugyanaz a bemenet gyakorlatilag egyedi és megismételhetetlen, ha a linuxos példánál maradunk. 2 nagyon hasonló bemenet is teljesen más kimenetet ad.

A /dev/random-nak az a nagy hátárnya, hogy kifogy az entrópia gyorsan és nem szolgáltat újabb random-ot, ha nincs elég entrópia hozzá, márpedig gyakran nincs. A /dev/urandom is ugyanezt csinája csak azzal a különbséggel, hogy számol tovább ha nincs entrópia akkor is. Azonban, ha ez fontos, akkor van lehetőség venni is akár hardveres random generátort mely a kvantummechanikának köszönhetően állít elő valódi random-ot és be is konfigurálható hogy a /dev/random azt használja.

Ahol nagyon kritikusan fontos a kriptográfiára épülő biztonság. Pl banki tranzakciók, katonaság.

Mj.:

Amúgy meg annak is van létjogosultsága, hogy fix inicializálási értékkel számoljunk álvéletlen számokat, ha egy szimulációt akarunk többször lefuttatni.