Ang pseudo-random na numero ay isang espesyal na numero na nabuo ng isang espesyal na generator. Ang Deterministic Random Bit Generator (PRNG), na kilala rin bilang Deterministic Random Bit Generator (DRBG), ay isang algorithm para sa pagbuo ng isang sequence ng mga numero na ang mga katangian ay humigit-kumulang sa mga katangian ng random na mga sequence ng numero. Ang nabuong PRNG sequence ay hindi tunay na random, dahil ito ay ganap na tinutukoy ng isang seed value na tinatawag na PRNG seed, na maaaring kabilang ang tunay na random na mga value. Bagama't ang mga pagkakasunud-sunod na mas malapit sa random ay maaaring mabuo gamit ang hardware na random na mga generator ng numero, ang mga pseudo-random na mga generator ng numero ay mahalaga sa pagsasanay para sa bilis ng pagbuo ng mga numero at ang kanilang reproducibility.
Application
Ang mga
PRNG ay sentro sa mga application gaya ng simulation (hal. para sa Monte Carlo), mga electronic na laro (hal para sa procedural generation), at cryptography. Ang mga cryptographic na application ay nangangailangan na ang outputang data ay hindi mahuhulaan mula sa naunang impormasyon. Kinakailangan ang mas kumplikadong mga algorithm na hindi nagmana ng linearity ng mga simpleng PRNG.
Mga Tuntunin at Kundisyon
Ang magagandang istatistikal na katangian ay isang pangunahing kinakailangan para sa pagkuha ng PRNG. Sa pangkalahatan, kailangan ang maingat na pagsusuri sa matematika upang matiyak na ang RNG ay bumubuo ng mga numero na sapat na malapit sa random upang maging angkop para sa nilalayong paggamit.
Nagbabala si John von Neumann laban sa maling pagpapakahulugan sa PRNG bilang isang tunay na random na generator at nagbiro na "Sinumang nag-iisip ng mga pamamaraan ng aritmetika para sa pagbuo ng mga random na numero ay tiyak na nasa isang estado ng kasalanan."
Gamitin
Maaaring ilunsad ang
PRNG mula sa isang di-makatwirang paunang estado. Palagi itong bubuo ng parehong pagkakasunud-sunod kapag sinimulan sa estadong ito. Ang PRNG period ay tinukoy bilang mga sumusunod: maximum sa lahat ng mga unang estado ng haba ng hindi umuulit na prefix ng sequence. Ang panahon ay nililimitahan ng bilang ng mga estado, kadalasang sinusukat sa mga bit. Dahil posibleng dumoble ang haba ng panahon sa bawat idinagdag na bit na "estado", madaling gumawa ng mga PRNG na may mga tuldok na sapat na malaki para sa maraming praktikal na aplikasyon.
Kung ang panloob na estado ng PRNG ay naglalaman ng n bit, ang panahon nito ay maaaring hindi hihigit sa 2n resulta, ito ay mas maikli. Para sa ilang PRNG, maaaring kalkulahin ang tagal nang hindi nilalagpasan ang buong panahon. Karaniwan ang mga Linear Feedback Shift Registers (LFSRs).ay pinili upang magkaroon ng mga tuldok na katumbas ng 2n − 1.
Linear congruential generators ay may mga panahon na maaaring kalkulahin gamit ang factoring. Bagama't uulitin ng PPP ang mga resulta nito pagkatapos nilang maabot ang katapusan ng panahon, ang paulit-ulit na resulta ay hindi nangangahulugang naabot na ang katapusan ng panahon, dahil ang panloob na estado nito ay maaaring mas malaki kaysa sa output; lalo itong maliwanag para sa mga PRNG na may isang bit na output.
Posibleng mga error
Ang mga error na natagpuan ng mga may sira na PRNG ay mula sa banayad (at hindi alam) hanggang sa mga halata. Ang isang halimbawa ay ang RANDU random number algorithm, na ginamit sa mga mainframe sa loob ng ilang dekada. Ito ay isang malubhang pagkukulang, ngunit ang kakulangan nito ay hindi napansin sa mahabang panahon.
Sa maraming lugar, ang mga pag-aaral sa pananaliksik na gumamit ng random na seleksyon, Monte Carlo simulation, o iba pang pamamaraan na batay sa RNG ay hindi masyadong maaasahan kaysa sa maaaring maging resulta ng mahinang kalidad ng GNPG. Kahit ngayon, kailangan kung minsan ang pag-iingat, gaya ng pinatutunayan ng babala sa International Encyclopedia of Statistical Science (2010).
Matagumpay na case study
Bilang isang paglalarawan, isaalang-alang ang malawakang ginagamit na Java programming language. Simula noong 2017, umaasa pa rin ang Java sa Linear Congruential Generator (LCG) para sa PRNG nito.
Kasaysayan
Ang unang PRNG na umiwas sa mga seryosong problema at tumakbo pa rin ng medyo mabilis,ay ang Mersenne Twister (tinalakay sa ibaba), na inilathala noong 1998. Simula noon, binuo ang iba pang mataas na kalidad na PRNG.
Ngunit ang kasaysayan ng mga pseudo-random na numero ay hindi nagtatapos doon. Sa ikalawang kalahati ng ika-20 siglo, ang karaniwang klase ng mga algorithm na ginagamit para sa mga PRNG ay may kasamang mga linear na congruential generator. Ang kalidad ng LCG ay kilala na hindi sapat, ngunit mas mahusay na mga pamamaraan ay hindi magagamit. Inilarawan ng Press et al (2007) ang resulta tulad ng sumusunod: "Kung ang lahat ng siyentipikong papel na ang mga resulta ay may pagdududa dahil sa [LCGs at mga kaugnay na] nawala mula sa mga istante ng aklatan, magkakaroon ng puwang na kasing laki ng iyong kamao sa bawat istante."
Ang pangunahing tagumpay sa paglikha ng mga pseudo-random na generator ay ang pagpapakilala ng mga pamamaraan batay sa linear na paulit-ulit sa isang field na may dalawang elemento; ang mga naturang oscillator ay pinagsama sa mga linear na feedback shift registers. Nagsilbi silang batayan para sa pag-imbento ng mga pseudo-random na sensor ng numero.
Sa partikular, naiwasan ng 1997 na imbensyon ni Mersen Twister ang marami sa mga problema sa mga naunang generator. Ang Mersenne Twister ay may panahon na 219937−1 na mga pag-ulit (≈4.3 × 106001). Napatunayan na ito ay pantay na ipinamahagi sa (hanggang) 623 na mga dimensyon (para sa mga 32-bit na halaga), at sa panahon ng pagpapakilala nito ay mas mabilis kaysa sa iba pang mga generator ng tunog na istatistika na gumagawa ng mga pseudo-random na pagkakasunud-sunod ng numero.
Noong 2003, ipinakilala ni George Marsaglia ang isang pamilya ng mga generator ng xorshift batay din sa linear na pag-uulit. Ang mga generator na ito ay labisay mabilis at - pinagsama sa isang non-linear na operasyon - pumasa sila sa mahigpit na mga pagsusulit sa istatistika.
Noong 2006, binuo ang pamilya ng WELL generator. Ang mga WELL generator sa isang kahulugan ay nagpapahusay sa kalidad ng Twister Mersenne, na may napakalaking state space at napakabagal na pagbawi mula sa kanila, na bumubuo ng mga pseudo-random na numero na may maraming mga zero.
Cryptography
Ang
PRNG na angkop para sa mga cryptographic na application ay tinatawag na cryptographically secure PRNG (CSPRNG). Ang kinakailangan para sa isang CSPRNG ay ang isang umaatake na hindi alam ang binhi ay may marginal na kalamangan lamang sa pagkilala sa output sequence ng generator mula sa isang random na pagkakasunod-sunod. Sa madaling salita, habang ang isang PRNG ay kinakailangan lamang upang makapasa sa ilang partikular na istatistikal na pagsusulit, ang isang CSPRNG ay dapat pumasa sa lahat ng mga istatistikal na pagsusulit na limitado sa polynomial na oras sa laki ng binhi.
Bagama't ang patunay ng property na ito ay lampas sa kasalukuyang antas ng computational complexity theory, matibay na ebidensya ang maaaring ibigay sa pamamagitan ng pagbabawas ng CSPRNG sa isang problemang itinuturing na mahirap, tulad ng integer factorization. Sa pangkalahatan, maaaring kailanganin ang mga taon ng pagsusuri bago ma-certify ang isang algorithm bilang CSPRNG.
Ipinakita na malamang na nagpasok ang NSA ng asymmetric na pinto sa likod sa NIST-certified Dual_EC_DRBG pseudo-random number generator.
Pseudo-random na mga algorithmnumero
Karamihan sa mga PRNG algorithm ay gumagawa ng mga pagkakasunud-sunod na pantay na ipinamamahagi ng alinman sa ilang mga pagsubok. Ito ay isang bukas na tanong. Ito ay isa sa mga sentro sa teorya at kasanayan ng cryptography: mayroon bang paraan upang makilala ang output ng isang mataas na kalidad na PRNG mula sa isang tunay na random na pagkakasunud-sunod? Sa setting na ito, alam ng solver na alinman sa isang kilalang PRNG algorithm ang ginamit (ngunit hindi ang estado kung saan ito nasimulan), o isang tunay na random na algorithm ang ginamit. Dapat niyang makilala ang mga ito.
Ang seguridad ng karamihan sa mga cryptographic na algorithm at protocol na gumagamit ng mga PRNG ay batay sa pag-aakalang imposibleng makilala ang pagitan ng paggamit ng angkop na PRNG at ang paggamit ng isang tunay na random na pagkakasunud-sunod. Ang pinakasimpleng mga halimbawa ng dependency na ito ay ang mga stream cipher, na kadalasang gumagana sa pamamagitan ng pag-alis o pagpapadala ng plaintext na mensahe na may PRNG output, na gumagawa ng ciphertext. Ang pagdidisenyo ng mga PRNG na may sapat na cryptographically ay napakahirap dahil kailangan nilang matugunan ang mga karagdagang pamantayan. Ang laki ng panahon nito ay isang mahalagang salik sa pagiging angkop sa cryptographic ng isang PRNG, ngunit hindi ang isa lamang.
Ang isang maagang computer PRNG na iminungkahi ni John von Neumann noong 1946 ay kilala bilang mean squares method. Ang algorithm ay ang mga sumusunod: kumuha ng anumang numero, parisukat ito, alisin ang gitnang mga digit ng resultang numero bilang isang "random na numero", pagkatapos ay gamitin ang numerong ito bilang panimulang numero para sa susunod na pag-ulit. Halimbawa, ang pag-square ng numerong 1111 ay nagbibigay1234321, na maaaring isulat bilang 01234321, ang isang 8-digit na numero ay ang parisukat ng isang 4-digit na numero. Nagbibigay ito ng 2343 bilang isang "random" na numero. Ang resulta ng pag-uulit ng pamamaraang ito ay 4896, at iba pa. Gumamit si Von Neumann ng 10 digit na numero, ngunit pareho ang proseso.
Mga disadvantage ng "middle square"
Ang problema sa pamamaraang "mean square" ay ang lahat ng mga sequence sa kalaunan ay umuulit, ang ilan ay napakabilis, halimbawa: 0000. Alam ni Von Neumann ang tungkol dito, ngunit nakakita siya ng isang diskarte na sapat para sa kanyang mga layunin, at nag-aalala na ang Itatago lang ng "corrections" sa matematika ang mga error sa halip na alisin ang mga ito.
Nakita ni Von Neumann na hindi angkop ang mga generator ng hardware na random at pseudo-random na numero: kung hindi nila naitala ang nabuong output, hindi na sila masusuri kung may mga error sa ibang pagkakataon. Kung isusulat nila ang kanilang mga resulta, mauubos nila ang limitadong magagamit na memorya ng computer at sa gayon ang kakayahan ng computer na magbasa at magsulat ng mga numero. Kung ang mga numero ay nakasulat sa mga kard, mas magtatagal ang mga ito sa pagsulat at pagbabasa. Sa ENIAC computer na ginamit niya, ang "middle square" na paraan at isinagawa ang proseso ng pagkuha ng mga pseudo-random na numero nang ilang daang beses na mas mabilis kaysa sa pagbabasa ng mga numero mula sa mga punched card.
Mean square ay pinalitan na ng mas kumplikadong mga generator.
Makabagong paraan
Ang isang kamakailang inobasyon ay ang pagsamahin ang mean square sa Weil sequence. Tinitiyak ng pamamaraang ito ang mataas na kalidad ng mga produkto sa loobmahabang panahon. Nakakatulong na makuha ang pinakamahusay na pseudo-random na mga formula ng numero.
