Pseudoatsitiktinis skaičius yra specialus skaičius, sugeneruotas specialiu generatoriumi. Deterministinis atsitiktinių bitų generatorius (PRNG), taip pat žinomas kaip Deterministinis atsitiktinių bitų generatorius (DRBG), yra algoritmas, skirtas generuoti skaičių seką, kurios savybės apytiksliai atitinka atsitiktinių skaičių sekų charakteristikas. Sukurta PRNG seka nėra tikrai atsitiktinė, nes ją visiškai lemia pradinė vertė, vadinama PRNG sėkla, kuri gali apimti tikrai atsitiktines reikšmes. Nors sekas, kurios yra artimesnės atsitiktinumui, gali būti generuojamos naudojant aparatinius atsitiktinių skaičių generatorius, pseudoatsitiktinių skaičių generatoriai praktikoje yra svarbūs skaičių generavimo greičiui ir jų atkuriamumui.
Programa
PRNG yra pagrindinės tokiose programose kaip modeliavimas (pvz., Monte Karlo), elektroniniai žaidimai (pvz., procedūrų generavimui) ir kriptografija. Kriptografijos programos reikalauja, kad išvestisduomenys nebuvo nuspėti iš ankstesnės informacijos. Reikalingi sudėtingesni algoritmai, kurie nepaveldėtų paprastų PRNG tiesiškumo.
Taisyklės ir sąlygos
Geros statistinės savybės yra pagrindinis reikalavimas norint gauti PRNG. Apskritai, norint įsitikinti, kad RNG generuoja skaičius, pakankamai artimus atsitiktiniams, reikia kruopščios matematinės analizės, kad būtų tinkami numatytam naudojimui.
John von Neumann perspėjo neteisingai interpretuoti PRNG kaip tikrai atsitiktinių generatorių ir pajuokavo, kad „Kiekvienas, kuris atsižvelgia į aritmetinius atsitiktinių skaičių generavimo metodus, tikrai yra nuodėmės būsenoje“.
Naudoti
PRNG galima paleisti iš savavališkos pradinės būsenos. Ji visada generuos tą pačią seką, kai bus inicijuota su šia būsena. PRNG laikotarpis apibrėžiamas taip: maksimalus per visas pradines nesikartojančios sekos priešdėlio ilgio būsenas. Laikotarpį riboja būsenų skaičius, paprastai matuojamas bitais. Kadangi periodo ilgis gali padvigubėti pridėjus kiekvieną „būsenos“bitą, nesunku sukurti PRNG su pakankamai dideliais laikotarpiais daugeliui praktinių pritaikymų.
Jei PRNG vidinėje būsenoje yra n bitų, jo periodas gali būti ne didesnis nei 2n rezultatų, jis yra daug trumpesnis. Kai kurių PRNG trukmė gali būti skaičiuojama neaplenkiant viso laikotarpio. Paprastai yra linijiniai grįžtamojo ryšio poslinkių registrai (LFSR).parenkami taip, kad periodai būtų lygūs 2n − 1.
Tiesiniai kongruenciniai generatoriai turi periodus, kuriuos galima apskaičiuoti naudojant faktoringą. Nors PPP pakartos savo rezultatus po to, kai pasieks laikotarpio pabaigą, pakartotinis rezultatas nereiškia, kad buvo pasiekta laikotarpio pabaiga, nes jo vidinė būsena gali būti didesnė už išvestį; tai ypač akivaizdu PRNG su vieno bito išvestimi.
Galimos klaidos
Defektuotų PRNG aptiktų klaidų yra nuo subtilių (ir nežinomų) iki akivaizdžių. Pavyzdys yra RANDU atsitiktinių skaičių algoritmas, kuris buvo naudojamas dideliuose kompiuteriuose dešimtmečius. Tai buvo rimtas trūkumas, tačiau jo netinkamumas buvo nepastebėtas ilgą laiką.
Daugelyje sričių moksliniai tyrimai, kuriuose buvo naudojama atsitiktinė atranka, Monte Karlo modeliavimas ar kiti RNG pagrįsti metodai, yra daug mažiau patikimi, nei galėtų būti prastos kokybės GNPG rezultatas. Net ir šiandien kartais reikia būti atsargiems, kaip rodo įspėjimas Tarptautinėje statistikos mokslų enciklopedijoje (2010).
Sėkmingas atvejo tyrimas
Kaip iliustracija, apsvarstykite plačiai naudojamą Java programavimo kalbą. Nuo 2017 m. „Java“PRNG vis dar naudoja linijinį kongruentinį generatorių (LCG).
Istorija
Pirmasis PRNG, skirtas išvengti rimtų problemų ir vis tiek veikti gana greitai,buvo Mersenne Twister (aptartas toliau), kuris buvo išleistas 1998 m. Nuo tada buvo sukurti kiti aukštos kokybės PRNG.
Tačiau pseudoatsitiktinių skaičių istorija tuo nesibaigia. XX amžiaus antroje pusėje standartinė PRNG algoritmų klasė apėmė tiesinius kongruencinius generatorius. Buvo žinoma, kad LCG kokybė buvo netinkama, tačiau geresnių metodų nebuvo. Press ir kt. (2007) rezultatą apibūdino taip: „Jei visi moksliniai straipsniai, kurių rezultatai kelia abejonių dėl [LCG ir susijusių], išnyktų iš bibliotekos lentynų, kiekvienoje lentynoje atsirastų jūsų kumščio dydžio tarpas.
Pagrindinis pasiekimas kuriant pseudoatsitiktinius generatorius buvo metodų, pagrįstų tiesiniu pasikartojimu dviejų elementų lauke, įdiegimas; tokie osciliatoriai yra sujungti su linijinio grįžtamojo ryšio poslinkių registrais. Jie buvo pseudoatsitiktinių skaičių jutiklių išradimo pagrindas.
Ypač 1997 m. Merseno Twisterio išradimas išvengė daugelio ankstesnių generatorių problemų. Mersenne Twister turi 219937–1 iteracijų periodą (≈4,3 × 106001). Įrodyta, kad jis yra tolygiai paskirstytas (iki) 623 matmenų (32 bitų reikšmėms), o įvedimo metu buvo greitesnis nei kiti statistiškai patikimi generatoriai, sukuriantys pseudoatsitiktinių skaičių sekas.
2003 m. George'as Marsaglia pristatė xorshift generatorių šeimą, taip pat pagrįstą linijiniu pasikartojimu. Šie generatoriai yra nepaprastaiyra greiti ir kartu su nelinijine operacija išlaiko griežtus statistinius testus.
2006 m. buvo sukurta WELL generatorių šeima. WELL generatoriai tam tikra prasme pagerina Twister Mersenne kokybę, kuri turi per didelę būsenų erdvę ir labai lėtą atkūrimą iš jų generuoja pseudoatsitiktinius skaičius su daugybe nulių.
Kriptografija
PRNG, tinkamas kriptografinėms programoms, vadinamas kriptografiškai saugiu PRNG (CSPRNG). CSPRNG reikalavimas yra tas, kad užpuolikas, nežinantis pradinės sekos, turėtų tik nedidelį pranašumą atskirdamas generatoriaus išvesties seką nuo atsitiktinės sekos. Kitaip tariant, nors PRNG reikalingas tik tam, kad išlaikytų tam tikrus statistinius testus, CSPRNG turi išlaikyti visus statistinius testus, kurie ribojami iki daugianario sėklos dydžio.
Nors šios savybės įrodymas viršija dabartinį skaičiavimo sudėtingumo teorijos lygį, galima pateikti svarių įrodymų, sumažinus CSPRNG iki problemos, kuri laikoma sudėtinga, pavyzdžiui, sveikųjų skaičių faktorizavimas. Apskritai, norint sertifikuoti algoritmą kaip CSPRNG, gali prireikti metų peržiūros.
Buvo parodyta, kad tikėtina, kad NSA įterpė asimetrines galines duris į NIST sertifikuotą Dual_EC_DRBG pseudoatsitiktinių skaičių generatorių.
Pseudoatsitiktiniai algoritmaiskaičiai
Dauguma PRNG algoritmų sukuria sekas, kurios yra tolygiai paskirstytos bet kuriuo iš kelių testų. Tai atviras klausimas. Tai vienas iš svarbiausių kriptografijos teorijoje ir praktikoje: ar yra būdas atskirti aukštos kokybės PRNG išvestį nuo tikrai atsitiktinės sekos? Šiame nustatyme sprendėjas žino, kad buvo naudojamas žinomas PRNG algoritmas (bet ne būsena, su kuria jis buvo inicijuotas), arba buvo naudojamas tikrai atsitiktinis algoritmas. Jis turi juos atskirti.
Daugelio kriptografinių algoritmų ir protokolų, naudojančių PRNG, saugumas pagrįstas prielaida, kad neįmanoma atskirti tinkamo PRNG ir tikrai atsitiktinės sekos naudojimo. Paprasčiausi šios priklausomybės pavyzdžiai yra srauto šifrai, kurie dažniausiai veikia praleidžiant arba siunčiant paprasto teksto pranešimą su PRNG išvestimi, sukuriant šifruotą tekstą. Sukurti kriptografiškai tinkamus PRNG yra labai sunku, nes jie turi atitikti papildomus kriterijus. Jo laikotarpio dydis yra svarbus veiksnys, lemiantis PRNG kriptografinį tinkamumą, bet ne vienintelis.
Ankstyvasis kompiuterinis PRNG, kurį 1946 m. pasiūlė Johnas von Neumannas, yra žinomas kaip vidutinių kvadratų metodas. Algoritmas yra toks: paimkite bet kurį skaičių, padėkite jį kvadratu, pašalinkite gauto skaičiaus vidurinius skaitmenis kaip „atsitiktinį skaičių“, tada naudokite šį skaičių kaip kitos iteracijos pradinį skaičių. Pavyzdžiui, skaičių 1111 padalijus kvadratu, gaunama1234321, kurį galima parašyti kaip 01234321, 8 skaitmenų skaičius yra 4 skaitmenų skaičiaus kvadratas. Tai suteikia 2343 kaip „atsitiktinį“skaičių. Šios procedūros pakartojimo rezultatas yra 4896 ir pan. Von Neumannas naudojo 10 skaitmenų skaičius, tačiau procesas buvo toks pat.
Vidurinės aikštės trūkumai
„Vidutinio kvadrato“metodo problema yra ta, kad visos sekos galiausiai kartojasi, kai kurios labai greitai, pavyzdžiui: 0000. Von Neumannas apie tai žinojo, bet rado metodą, kurio pakanka jo tikslams, ir nerimavo, kad matematikos „taisymai“tiesiog paslėptų klaidas, o ne jas pašalintų.
Von Neumann nustatė, kad aparatinės įrangos atsitiktinių ir pseudoatsitiktinių skaičių generatoriai yra netinkami: jei jie neįrašo sugeneruotos išvesties, vėliau nebus galima patikrinti, ar nėra klaidų. Jei jie užsirašytų savo rezultatus, jie išnaudotų ribotą laisvą kompiuterio atmintį, taigi ir kompiuterio galimybes skaityti bei rašyti skaičius. Jei ant kortelių būtų rašomi skaičiai, jų rašymas ir skaitymas užtruktų daug ilgiau. ENIAC kompiuteryje jis naudojo „vidurinio kvadrato“metodą ir atliko pseudoatsitiktinių skaičių gavimo procesą kelis šimtus kartų greičiau, nei nuskaito skaičius iš perforuotų kortelių.
Vidutinį kvadratą nuo to laiko pakeitė sudėtingesni generatoriai.
Inovatyvus metodas
Naujausia naujovė yra sujungti vidutinį kvadratą su Weil seka. Šis metodas užtikrina aukštą produktų kokybęilgas laikotarpis. Tai padeda gauti geriausias pseudoatsitiktinių skaičių formules.
