Pseudosatunnaisluku on erityisen generaattorin luoma erikoisluku. Deterministinen satunnaisbittigeneraattori (PRNG), joka tunnetaan myös nimellä Deterministic Random Bit Generator (DRBG), on algoritmi, jolla luodaan lukujono, jonka ominaisuudet vastaavat satunnaislukusekvenssien ominaisuuksia. Luotu PRNG-sekvenssi ei ole todella satunnainen, koska sen määrittää kokonaan PRNG-siemeneksi kutsuttu siemenarvo, joka voi sisältää todella satunnaisia arvoja. Vaikka satunnaislukugeneraattoreita lähempänä olevia sekvenssejä voidaan generoida laitteiston satunnaislukugeneraattoreilla, näennäissatunnaislukugeneraattorit ovat käytännössä tärkeitä numeroiden luomisen nopeuden ja toistettavuuden kann alta.
Hakemus
PRNG:t ovat keskeisiä sovelluksissa, kuten simuloinnissa (esim. Monte Carlossa), elektronisissa peleissä (esim. prosessin luomiseen) ja kryptografiassa. Salaussovellukset edellyttävät, että tulostiedot eivät olleet ennustettavissa aikaisemman tiedon perusteella. Tarvitaan monimutkaisempia algoritmeja, jotka eivät peri yksinkertaisten PRNG:iden lineaarisuutta.
Käyttöehdot
Hyvät tilastolliset ominaisuudet ovat keskeinen vaatimus PRNG:n saamiseksi. Yleisesti ottaen tarvitaan huolellista matemaattista analyysiä sen varmistamiseksi, että RNG luo numeroita, jotka ovat tarpeeksi lähellä satunnaisia ollakseen sopivia aiottuun käyttöön.
John von Neumann varoitti tulkitsemasta PRNG:tä väärin todellisena satunnaisgeneraattorina ja vitsaili, että "Jokainen, joka harkitsee aritmeettisia menetelmiä satunnaislukujen generoimiseksi, on varmasti syntitilassa."
Käytä
PRNG voidaan käynnistää mieliv altaisesta alkutilasta. Se luo aina saman sekvenssin, kun se alustetaan tässä tilassa. PRNG-jakso määritellään seuraavasti: ei-toistuvan sekvenssin etuliitteen pituuden kaikkien alkutilojen maksimi. Jaksoa rajoittaa tilojen lukumäärä, yleensä bitteinä mitattuna. Koska jakson pituus mahdollisesti kaksinkertaistuu jokaisen "tila"-bitin lisättyä, on helppoa luoda PRNG-kuvia, joiden jaksot ovat riittävän suuria moniin käytännön sovelluksiin.
Jos PRNG:n sisäinen tila sisältää n bittiä, sen jakso voi olla korkeintaan 2n tulosta, se on paljon lyhyempi. Joillekin PRNG:ille kesto voidaan laskea ohittamatta koko ajanjaksoa. Lineaariset palautesiirtorekisterit (LFSR) ovat tyypillisestivalitaan siten, että niiden jaksot ovat 2n − 1.
Lineaarisilla kongruenssigeneraattoreilla on jaksoja, jotka voidaan laskea factoringin avulla. Vaikka PPP toistaa tulokset, kun ne saavuttavat jakson lopun, toistuva tulos ei tarkoita, että jakson loppu on saavutettu, koska sen sisäinen tila voi olla suurempi kuin tuotos; tämä on erityisen ilmeistä PRNG:issä, joissa on yksibittinen ulostulo.
Mahdolliset virheet
Viallisten PRNG-tiedostojen löytämät virheet vaihtelevat hienovaraisista (ja tuntemattomista) ilmeisiin. Esimerkkinä on satunnaislukualgoritmi RANDU, jota on käytetty keskuskoneissa vuosikymmeniä. Se oli vakava puute, mutta sen riittämättömyys jäi huomaamatta pitkään.
Monilla alueilla tutkimukset, joissa on käytetty satunnaisvalintaa, Monte Carlo -simulaatioita tai muita RNG:hen perustuvia menetelmiä, ovat paljon vähemmän luotettavia kuin huonolaatuisen GNPG:n tulos. Jopa nykyäänkin varovaisuutta vaaditaan toisinaan, kuten International Encyclopedia of Statistical Science (2010) -julkaisussa oleva varoitus osoittaa.
Onnistunut tapaustutkimus
Havainnollistaa esimerkkinä laaj alti käytettyä Java-ohjelmointikieltä. Vuodesta 2017 lähtien Java luottaa PRNG:ään edelleen Linear Congruential Generatoriin (LCG).
Historia
Ensimmäinen PRNG, joka välttää vakavia ongelmia ja toimii silti melko nopeasti,oli Mersenne Twister (käsitellään alla), joka julkaistiin vuonna 1998. Sen jälkeen on kehitetty muita korkealaatuisia PRNG:itä.
Mutta näennäissatunnaisten lukujen historia ei lopu tähän. 1900-luvun toisella puoliskolla PRNG:issä käytetty standardi algoritmiluokka sisälsi lineaariset kongruenssigeneraattorit. LCG:n laadun tiedettiin olevan riittämätön, mutta parempia menetelmiä ei ollut saatavilla. Press et al (2007) kuvailivat tulosta seuraavasti: "Jos kaikki tieteelliset artikkelit, joiden tulokset ovat epäselviä [LCG:n ja niihin liittyvien] vuoksi, katoaisivat kirjastojen hyllyistä, jokaisessa hyllyssä olisi nyrkkisi kokoinen rako."
Pääasiallinen saavutus näennäissatunnaisten generaattoreiden luomisessa oli lineaariseen toistumiseen perustuvien menetelmien käyttöönotto kaksielementtisessä kentässä; tällaiset oskillaattorit on kytketty lineaarisiin takaisinkytkentäsiirtorekistereihin. Ne toimivat perustana pseudosatunnaislukuanturien keksimiselle.
Erityisesti Mersen Twisterin vuonna 1997 tekemä keksintö vältti monet aikaisempien generaattoreiden ongelmista. Mersenne Twisterin jakso on 219937–1 iteraatiota (≈4,3 × 106001). Sen on osoitettu jakautuneen tasaisesti (jopa) 623 ulottuvuuteen (32-bittisille arvoille), ja se oli käyttöönottohetkellä nopeampi kuin muut tilastollisesti luotettavat generaattorit, jotka tuottavat näennäissatunnaisia lukusarjoja.
Vuonna 2003 George Marsaglia esitteli xorshift-generaattoreiden perheen, jotka perustuvat myös lineaariseen toistoon. Nämä generaattorit ovat erittäinovat nopeita ja - yhdistettynä epälineaariseen operaatioon - läpäisevät tiukat tilastolliset testit.
Vuonna 2006 kehitettiin WELL-generaattoriperhe. WELL-generaattorit parantavat tavallaan Twister Mersennen laatua, sillä sillä on liian suuri tila-avaruus ja erittäin hidas toipuminen niistä luoden näennäissatunnaisia lukuja, joissa on paljon nollia.
Salaus
PRNG:tä, joka sopii kryptografisiin sovelluksiin, kutsutaan kryptografisesti suojatuksi PRNG:ksi (CSPRNG). CSPRNG:n vaatimus on, että hyökkääjällä, joka ei tunne siementä, on vain marginaalinen etu erottaa generaattorin lähtösekvenssi satunnaisesta sekvenssistä. Toisin sanoen, vaikka PRNG:n vaaditaan vain läpäisemään tietyt tilastolliset testit, CSPRNG:n on läpäistävä kaikki tilastolliset testit, jotka rajoittuvat siemenkoon polynomiaikaan.
Vaikka todiste tästä ominaisuudesta ylittää nykyisen laskennallisen monimutkaisuusteorian tason, voidaan saada vahvaa näyttöä pelkistämällä CSPRNG vaikeaksi pidetyksi ongelmaksi, kuten kokonaislukujen tekijöihin jako. Yleensä voidaan vaatia vuosien tarkistus ennen kuin algoritmi voidaan sertifioida CSPRNG:ksi.
On osoitettu, että on todennäköistä, että NSA lisäsi epäsymmetrisen takaoven NIST-sertifioituun Dual_EC_DRBG pseudosatunnaislukugeneraattoriin.
Pseudosatunnaisalgoritmitnumerot
Useimmat PRNG-algoritmit tuottavat sekvenssejä, jotka jakautuvat tasaisesti millä tahansa useista testeistä. Tämä on avoin kysymys. Se on yksi keskeisistä kryptografian teoriassa ja käytännössä: onko olemassa tapaa erottaa korkealaatuisen PRNG:n tulos todella satunnaisesta sekvenssistä? Tässä asetuksessa ratkaisija tietää, että käytettiin joko tunnettua PRNG-algoritmia (mutta ei tilaa, jolla se alustettiin) tai todella satunnaista algoritmia. Hänen on erotettava ne toisistaan.
Useimpien PRNG:itä käyttävien salausalgoritmien ja protokollien turvallisuus perustuu olettamukseen, että on mahdotonta erottaa sopivan PRNG:n käyttöä todella satunnaisen sekvenssin käytöstä. Yksinkertaisimpia esimerkkejä tästä riippuvuudesta ovat stream-salaukset, jotka useimmiten toimivat jättämällä pois tai lähettämällä selväkielisen viestin PRNG-lähdöllä, tuottaen salatekstin. Krypografisesti riittävien PRNG:iden suunnittelu on erittäin vaikeaa, koska niiden on täytettävä lisäkriteerit. Sen jakson koko on tärkeä tekijä PRNG:n kryptografisessa soveltuvuudessa, mutta ei ainoa.
John von Neumannin vuonna 1946 ehdottama varhainen tietokone PRNG tunnetaan keskineliömenetelmänä. Algoritmi on seuraava: ota mikä tahansa luku, neliöi se, poista tuloksena olevan luvun keskimmäiset numerot "satunnaislukuna" ja käytä sitten tätä numeroa seuraavan iteroinnin aloitusnumerona. Esimerkiksi luvun 1111 neliöinti antaa1234321, joka voidaan kirjoittaa muodossa 01234321, 8-numeroinen luku on 4-numeroisen luvun neliö. Tämä antaa 2343 "satunnaislukuna". Tämän menettelyn toistamisen tulos on 4896 ja niin edelleen. Von Neumann käytti 10-numeroisia lukuja, mutta prosessi oli sama.
"Keskiruudun" haitat
Mean square -menetelmän ongelma on, että kaikki sekvenssit toistuvat lopulta, jotkut hyvin nopeasti, esimerkiksi: 0000. Von Neumann tiesi tämän, mutta hän löysi tarkoituksiinsa riittävän lähestymistavan ja oli huolissaan siitä, että matemaattiset "korjaukset" vain piilottaisivat virheet sen sijaan, että ne poistaisivat niitä.
Von Neumann piti laitteiston satunnais- ja näennäissatunnaislukugeneraattorit sopimattomina: jos ne eivät tallenna generoitua tulosta, niitä ei voida tarkistaa myöhemmin virheiden var alta. Jos he kirjoittaisivat tulokset muistiin, he kuluttaisivat tietokoneen rajallisen muistin ja siten tietokoneen kyvyn lukea ja kirjoittaa numeroita. Jos numerot kirjoitettaisiin korteille, niiden kirjoittaminen ja lukeminen kestäisi paljon kauemmin. Hän käytti ENIAC-tietokoneessa "keskineliön" menetelmää ja suoritti pseudosatunnaislukujen saamisen useita satoja kertoja nopeammin kuin lukujen lukeminen reikäkorteilta.
Keskineliö on sittemmin korvattu monimutkaisemmilla generaattoreilla.
Innovatiivinen menetelmä
Viimeaikainen innovaatio on yhdistää keskineliö Weil-sekvenssiin. Tämä menetelmä takaa korkealaatuiset tuotteet sisälläpitkä aika. Se auttaa saamaan parhaat pseudosatunnaislukukaavat.
