Pseidogadījuma skaitlis ir īpašs skaitlis, ko ģenerē īpašs ģenerators. Deterministiskais nejaušības bitu ģenerators (PRNG), pazīstams arī kā deterministiskais nejaušības bitu ģenerators (DRBG), ir algoritms tādu skaitļu virknes ģenerēšanai, kuru īpašības aptuveni atbilst nejaušu skaitļu secību īpašībām. Ģenerētā PRNG secība nav īsti nejauša, jo to pilnībā nosaka sākuma vērtība, ko sauc par PRNG sēklu, kas var ietvert patiesi nejaušas vērtības. Lai gan secības, kas ir tuvākas nejaušībai, var ģenerēt, izmantojot aparatūras nejaušo skaitļu ģeneratorus, praksē pseidogadījuma skaitļu ģeneratori ir svarīgi skaitļu ģenerēšanas ātrumam un to reproducējamībai.
Pieteikums
PRNG ir galvenā nozīme tādās lietojumprogrammās kā simulācija (piemēram, Montekarlo), elektroniskās spēles (piemēram, procesuālai ģenerēšanai) un kriptogrāfija. Kriptogrāfijas lietojumprogrammām ir nepieciešama izvadedati nebija paredzami no iepriekšējās informācijas. Ir nepieciešami sarežģītāki algoritmi, kas nepārmanto vienkāršu PRNG linearitāti.
Noteikumi un nosacījumi
Labas statistiskās īpašības ir galvenā prasība PRNG iegūšanai. Kopumā ir nepieciešama rūpīga matemātiska analīze, lai pārliecinātos, ka RNG ģenerē skaitļus, kas ir pietiekami tuvu nejaušībai, lai būtu piemēroti paredzētajam lietojumam.
Džons fon Neumans brīdināja par nepareizu PRNG kā patiesi nejaušības ģeneratora interpretāciju un jokoja, ka "Ikviens, kurš ņem vērā aritmētiskās metodes nejaušu skaitļu ģenerēšanai, noteikti ir grēkā."
Izmantot
PRNG var palaist no patvaļīga sākuma stāvokļa. Inicializējot ar šo stāvokli, tas vienmēr ģenerēs to pašu secību. PRNG periods ir definēts šādi: maksimums visos neatkārtotās secības prefiksa garuma sākotnējos stāvokļos. Periodu ierobežo stāvokļu skaits, ko parasti mēra bitos. Tā kā perioda garums potenciāli dubultojas ar katru pievienoto "stāvokļa" bitu, ir viegli izveidot PRNG ar pietiekami lieliem periodiem daudziem praktiskiem lietojumiem.
Ja PRNG iekšējais stāvoklis satur n bitus, tā periods nevar būt lielāks par 2n rezultātiem, tas ir daudz īsāks. Dažiem PRNG ilgumu var aprēķināt, neapejot visu periodu. Lineārās atgriezeniskās saites maiņas reģistri (LFSR) parasti irir izvēlēti tā, lai periodi būtu vienādi ar 2n − 1.
Lineārajiem kongruenciālajiem ģeneratoriem ir periodi, kurus var aprēķināt, izmantojot faktoringu. Lai gan PPP atkārtos savus rezultātus pēc perioda beigu sasniegšanas, atkārtots rezultāts nenozīmē, ka ir sasniegts perioda beigas, jo tā iekšējais stāvoklis var būt lielāks par iznākumu; tas ir īpaši acīmredzams PRNG ar viena bita izvadi.
Iespējamas kļūdas
Bojātu PRNG atrasto kļūdu diapazons ir no smalkām (un nezināmām) līdz acīmredzamām. Piemērs ir RANDU nejaušo skaitļu algoritms, kas ir izmantots lieldatoros gadu desmitiem. Tas bija nopietns trūkums, taču tā neatbilstība ilgu laiku palika nepamanīta.
Daudzās jomās pētījumi, kuros izmantota nejauša atlase, Montekarlo simulācijas vai citas metodes, kuru pamatā ir RNG, ir daudz mazāk ticami, nekā tas varētu būt sliktas kvalitātes GNPG rezultāts. Pat mūsdienās dažkārt ir nepieciešama piesardzība, par ko liecina brīdinājums Starptautiskajā statistikas zinātņu enciklopēdijā (2010).
Veiksmīga gadījuma izpēte
Piemēram, apsveriet plaši izmantoto Java programmēšanas valodu. Sākot no 2017. gada, Java joprojām paļaujas uz lineāro kongruenciālo ģeneratoru (LCG) savam PRNG.
Vēsture
Pirmais PRNG, lai izvairītos no nopietnām problēmām un joprojām darbotos diezgan ātri,bija Mersenne Twister (apskatīts tālāk), kas tika publicēts 1998. gadā. Kopš tā laika ir izstrādāti citi augstas kvalitātes PRNG.
Bet ar to pseidogadījuma skaitļu vēsture nebeidzas. 20. gadsimta otrajā pusē PRNG izmantoto algoritmu standarta klase ietvēra lineāros kongruciālos ģeneratorus. Zināms, ka LCG kvalitāte bija nepietiekama, taču labākas metodes nebija pieejamas. Press et al (2007) rezultātu aprakstīja šādi: "Ja visi zinātniskie raksti, kuru rezultāti ir apšaubāmi [LCG un saistīto] dēļ, pazustu no bibliotēku plauktiem, katrā plauktā būtu jūsu dūres izmēra atstarpe."
Galvenais sasniegums pseidogadījuma ģeneratoru izveidē bija tādu metožu ieviešana, kuru pamatā ir lineāra atkārtošanās divu elementu laukā; šādi oscilatori ir savienoti ar lineārās atgriezeniskās saites nobīdes reģistriem. Tie kalpoja par pamatu pseidogadījuma skaitļu sensoru izgudrošanai.
Jo īpaši, Mersen Twister 1997. gada izgudrojums novērsa daudzas problēmas ar agrākiem ģeneratoriem. Mersenne Twister ir 219937–1 iterācijas periods (≈4,3 × 106001). Ir pierādīts, ka tas ir vienmērīgi sadalīts (līdz) 623 dimensijās (32 bitu vērtībām), un tā ieviešanas laikā tas bija ātrāks nekā citi statistiski pamatoti ģeneratori, kas rada pseidogadījuma skaitļu secības.
2003. gadā Džordžs Marsaglia ieviesa xorshift ģeneratoru saimi, kas arī balstījās uz lineāru atkārtošanos. Šie ģeneratori ir ārkārtīgiir ātri un kopā ar nelineāru darbību tie iztur stingrus statistikas testus.
2006. gadā tika izstrādāta WELL ģeneratoru saime. WELL ģeneratori savā ziņā uzlabo Twister Mersenne kvalitāti, kam ir pārāk liela stāvokļu telpa un ļoti lēna atkopšanās no tiem, ģenerējot pseidogadījuma skaitļus ar daudzām nullēm.
Kriptogrāfija
PRNG, kas piemērots kriptogrāfijas lietojumprogrammām, tiek saukts par kriptogrāfiski drošu PRNG (CSPRNG). CSPRNG prasība ir tāda, ka uzbrucējam, kurš nezina sēklu, ir tikai neliela priekšrocība, lai atšķirtu ģeneratora izvades secību no nejaušas secības. Citiem vārdiem sakot, lai gan PRNG ir nepieciešams tikai noteiktu statistikas testu nokārtošanai, CSPRNG ir jāiztur visi statistikas testi, kas ir ierobežoti līdz polinoma laikam sēklu lielumā.
Lai gan šīs īpašības pierādījums pārsniedz pašreizējo skaitļošanas sarežģītības teorijas līmeni, pārliecinošus pierādījumus var iegūt, samazinot CSPRNG līdz problēmai, kas tiek uzskatīta par sarežģītu, piemēram, veselu skaitļu faktorizāciju. Parasti var būt nepieciešams vairākus gadus pārskatīt algoritmu, lai to varētu sertificēt kā CSPRNG.
Ir pierādīts, ka, visticamāk, NSA ievietoja asimetriskas aizmugurējās durvis NIST sertificētajā Dual_EC_DRBG pseidogadījuma skaitļu ģeneratorā.
Pseidogadījuma algoritmicipari
Lielākā daļa PRNG algoritmu rada secības, kuras vienmērīgi sadala jebkurā no vairākiem testiem. Tas ir atklāts jautājums. Tas ir viens no galvenajiem kriptogrāfijas teorijā un praksē: vai ir veids, kā atšķirt augstas kvalitātes PRNG izvadi no patiesi nejaušas secības? Šajā iestatījumā atrisinātājs zina, ka tika izmantots zināms PRNG algoritms (bet ne stāvoklis, ar kuru tas tika inicializēts), vai arī tika izmantots patiesi nejaušs algoritms. Viņam tie ir jānošķir.
Lielākā daļa kriptogrāfijas algoritmu un protokolu, kas izmanto PRNG, drošība ir balstīta uz pieņēmumu, ka nav iespējams atšķirt piemērota PRNG un patiesi nejaušas secības izmantošanu. Vienkāršākie šīs atkarības piemēri ir straumes šifri, kas visbiežāk darbojas, izlaižot vai nosūtot vienkāršā teksta ziņojumu ar PRNG izvadi, veidojot šifrētu tekstu. Kriptogrāfiski atbilstošu PRNG izstrāde ir ārkārtīgi sarežģīta, jo tiem jāatbilst papildu kritērijiem. Perioda lielums ir svarīgs PRNG kriptogrāfiskās piemērotības faktors, taču ne vienīgais.
Agrīnā datora PRNG, ko 1946. gadā ierosināja Džons fon Neimans, sauc par vidējo kvadrātu metodi. Algoritms ir šāds: paņemiet jebkuru skaitli, salieciet to kvadrātā, noņemiet iegūtā skaitļa vidējos ciparus kā "izlases skaitli", pēc tam izmantojiet šo skaitli kā sākuma skaitli nākamajai iterācijai. Piemēram, skaitļa 1111 sagriešana kvadrātā dod1234321, ko var rakstīt kā 01234321, 8 ciparu skaitlis ir četrciparu skaitļa kvadrāts. Tas dod 2343 kā "izlases" skaitli. Šīs procedūras atkārtošanas rezultāts ir 4896 utt. Fon Noimans izmantoja 10 ciparu skaitļus, taču process bija tāds pats.
"Vidējā laukuma" trūkumi
Problēma ar "vidējā kvadrāta" metodi ir tāda, ka visas secības galu galā atkārtojas, dažas ļoti ātri, piemēram: 0000. Fon Noimans par to zināja, taču viņš atrada saviem mērķiem pietiekamu pieeju un uztraucās, ka matemātikas "labojumi" vienkārši paslēptu kļūdas, nevis tās noņemtu.
Fons Neimans uzskatīja, ka aparatūras izlases un pseidogadījuma skaitļu ģeneratori nav piemēroti: ja tie neieraksta ģenerēto izvadi, vēlāk tos nevar pārbaudīt, vai nav kļūdu. Ja viņi pierakstītu savus rezultātus, tie izsmeltu datora ierobežoto pieejamo atmiņu un tādējādi datora spēju lasīt un rakstīt skaitļus. Ja skaitļus rakstītu uz kartītēm, to rakstīšana un lasīšana prasītu daudz ilgāku laiku. Datorā ENIAC viņš izmantoja "vidējā kvadrāta" metodi un veica pseidogadījuma skaitļu iegūšanas procesu vairākus simtus reižu ātrāk, nekā nolasīja skaitļus no perfokartēm.
Vidējo kvadrātu kopš tā laika ir aizstājuši sarežģītāki ģeneratori.
Inovatīva metode
Pēdējais jauninājums ir apvienot vidējo kvadrātu ar Veila secību. Šī metode nodrošina augstas kvalitātes produktus iekšāilgs periods. Tas palīdz iegūt vislabākās pseidogadījuma skaitļu formulas.
