Nambari bandia-nasibu ni nambari maalum inayozalishwa na jenereta maalum. Deterministic Random Bit Generator (PRNG), pia inajulikana kama Deterministic Random Bit Generator (DRBG), ni algoriti ya kuzalisha mfuatano wa nambari ambazo sifa zake zinakadiria sifa za mfuatano wa nambari nasibu. Mfuatano wa PRNG uliozalishwa si wa nasibu, kwani hubainishwa kabisa na thamani ya mbegu inayoitwa mbegu ya PRNG, ambayo inaweza kujumuisha thamani nasibu. Ingawa mfuatano ambao uko karibu na nasibu unaweza kuzalishwa kwa kutumia jenereta za nambari nasibu za maunzi, jenereta za nambari bandia ni muhimu kimatendo kwa kasi ya uzalishaji wa nambari na uzalishwaji wao tena.
Maombi
PRNG ni kitovu cha programu kama vile uigaji (km kwa Monte Carlo), michezo ya kielektroniki (km kuunda utaratibu), na kriptografia. Programu za kriptografia zinahitaji utoajidata haikutabirika kutokana na taarifa za awali. Kanuni changamano zaidi zinahitajika ambazo hazirithi usawa wa PRNGs rahisi.
Sheria na Masharti
Sifa nzuri za takwimu ni hitaji kuu la kupata PRNG. Kwa ujumla, uchanganuzi makini wa hisabati unahitajika ili kuhakikisha kuwa RNG inazalisha nambari ambazo ziko karibu vya kutosha na nasibu ili kufaa kwa matumizi yaliyokusudiwa.
John von Neumann alionya dhidi ya kutafsiri vibaya PRNG kama jenereta nasibu na akatania kwamba "Yeyote anayezingatia mbinu za hesabu za kuzalisha nambari nasibu hakika yuko katika hali ya dhambi."
Tumia
PRNG inaweza kuzinduliwa kutoka kwa hali ya awali ya kiholela. Itazalisha mlolongo sawa kila wakati inapoanzishwa na hali hii. Kipindi cha PRNG kinafafanuliwa kama ifuatavyo: upeo juu ya hali zote za awali za urefu wa kiambishi awali cha mfuatano usiojirudia. Muda ni mdogo na idadi ya majimbo, kwa kawaida hupimwa kwa bits. Kwa sababu urefu wa kipindi unaweza kuongezeka maradufu kwa kila biti ya "jimbo" ikiongezwa, ni rahisi kuunda PRNG na vipindi vikubwa vya kutosha kwa matumizi mengi ya vitendo.
Ikiwa hali ya ndani ya PRNG ina bits n, kipindi chake kinaweza kuwa kisichozidi matokeo 2n, ni kifupi zaidi. Kwa baadhi ya PRNGs, muda unaweza kuhesabiwa bila kupita kipindi chote. Rejesta za Ubadilishaji Maoni ya Linear (LFSRs) kwa kawaidahuchaguliwa ili kuwa na vipindi sawa na 2n − 1.
Jenereta za mstari zinazolingana zina vipindi vinavyoweza kukokotwa kwa kutumia kipengele. Ingawa PPP itarudia matokeo yake baada ya kufikia mwisho wa kipindi, matokeo yanayorudiwa haimaanishi kuwa mwisho wa kipindi umefikiwa, kwani hali yake ya ndani inaweza kuwa kubwa kuliko matokeo; hii ni dhahiri hasa kwa PRNG zilizo na biti moja towe.
Hitilafu zinazowezekana
Hitilafu zinazopatikana na PRNG zenye kasoro huanzia fiche (na zisizojulikana) hadi za dhahiri. Mfano ni algoriti ya nambari nasibu ya RANDU, ambayo imekuwa ikitumika kwenye fremu kuu kwa miongo kadhaa. Lilikuwa ni dosari kubwa, lakini upungufu wake haukuonekana kwa muda mrefu.
Katika maeneo mengi, tafiti za utafiti ambazo zimetumia uteuzi nasibu, uigaji wa Monte Carlo, au mbinu nyinginezo kulingana na RNG haziaminiki sana kuliko zinavyoweza kuwa matokeo ya ubora duni wa GNPG. Hata leo, wakati mwingine tahadhari inahitajika, kama inavyothibitishwa na onyo katika Encyclopedia ya Kimataifa ya Sayansi ya Takwimu (2010).
kifani kifani
Kama kielelezo, zingatia lugha ya programu ya Java inayotumika sana. Kufikia 2017, Java bado inategemea Linear Congruential Generator (LCG) kwa PRNG yake.
Historia
PRNG ya kwanza ili kuepuka matatizo makubwa na bado inaendesha haraka sana,ilikuwa Mersenne Twister (iliyojadiliwa hapa chini), ambayo ilichapishwa mnamo 1998. Tangu wakati huo, PRNG zingine za ubora wa juu zimetengenezwa.
Lakini historia ya nambari bandia za nasibu haishii hapo. Katika nusu ya pili ya karne ya 20, darasa la kawaida la algoriti zinazotumiwa kwa PRNGs zilijumuisha jenereta zinazolingana. Ubora wa LCG ulijulikana kuwa hautoshi, lakini mbinu bora zaidi hazikupatikana. Press et al (2007) walielezea matokeo kama ifuatavyo: "Ikiwa karatasi zote za kisayansi ambazo matokeo yake ni ya shaka kwa sababu ya [LCGs na kuhusiana] zitatoweka kutoka kwa rafu za maktaba, kungekuwa na pengo la ukubwa wa ngumi kwenye kila rafu."
Mafanikio makuu katika uundaji wa jenereta bandia-nasibu yalikuwa ni kuanzishwa kwa mbinu kulingana na urudiaji wa mstari katika uga wa vipengele viwili; oscillators vile ni pamoja na rejista za mabadiliko ya maoni ya mstari. Zilitumika kama msingi wa uvumbuzi wa vitambuzi vya nambari bandia.
Hasa, uvumbuzi wa 1997 na Mersen Twister uliepuka matatizo mengi ya jenereta za awali. Mersenne Twister ina muda wa marudio 219937−1 (≈4.3 × 106001). Imethibitishwa kuwa inasambazwa sawasawa katika (hadi) vipimo 623 (kwa thamani za biti 32), na wakati wa utangulizi wake ulikuwa wa kasi zaidi kuliko jenereta zingine zenye sauti za kitakwimu ambazo huzalisha mfuatano wa nambari bandia.
Mnamo 2003, George Marsaglia alianzisha familia ya jenereta za xorshift pia kulingana na marudio ya mstari. Jenereta hizi ni kubwa mnoni za haraka na - pamoja na operesheni isiyo ya mstari - hufaulu majaribio makali ya takwimu.
Mnamo 2006, familia ya jenereta ya WELL iliundwa. Jenereta za WELL kwa maana fulani huboresha ubora wa Twister Mersenne, ambayo ina nafasi kubwa zaidi ya hali na urejeshaji wa polepole sana kutoka kwayo, ikitoa nambari bandia za nasibu zenye sufuri nyingi.
Cryptografia
PRNG inayofaa kwa programu za kriptografia inaitwa PRNG iliyo salama kwa njia fiche (CSPRNG). Sharti la CSPRNG ni kwamba mshambulizi ambaye hajui mbegu ana faida ndogo tu katika kutofautisha mfuatano wa matokeo ya jenereta kutoka kwa mfuatano wa nasibu. Kwa maneno mengine, ingawa PRNG inahitajika tu kupita majaribio fulani ya takwimu, CSPRNG lazima ipitishe majaribio yote ya takwimu ambayo yamewekewa mipaka ya muda wa polynomial katika saizi ya mbegu.
Ingawa uthibitisho wa sifa hii ni zaidi ya kiwango cha sasa cha nadharia ya uchangamano ya hesabu, ushahidi dhabiti unaweza kutolewa kwa kupunguza CSPRNG kuwa tatizo ambalo linachukuliwa kuwa gumu, kama vile uwekaji nambari kamili. Kwa ujumla, miaka ya ukaguzi inaweza kuhitajika kabla ya algoriti iweze kuthibitishwa kama CSPRNG.
Imeonyeshwa kuwa kuna uwezekano kuwa NSA iliingiza mlango wa nyuma usiolinganishwa kwenye jenereta ya nambari bandia ya Dual_EC_DRBG iliyoidhinishwa na NIST.
Algoriti za uwongo-nasibunambari
Algoriti nyingi za PRNG hutoa mifuatano ambayo inasambazwa sawasawa na jaribio lolote kati ya kadhaa. Hili ni swali lililo wazi. Ni moja wapo ya msingi katika nadharia na mazoezi ya kriptografia: kuna njia ya kutofautisha matokeo ya PRNG ya hali ya juu kutoka kwa mlolongo wa nasibu kweli? Katika mpangilio huu, kisuluhishi kinajua kwamba algoriti ya PRNG inayojulikana ilitumiwa (lakini si hali ambayo ilianzishwa), au algoriti nasibu ilitumika. Lazima apambanue baina yao.
Usalama wa algoriti na itifaki nyingi za kriptografia zinazotumia PRNG unatokana na dhana kwamba haiwezekani kutofautisha kati ya matumizi ya PRNG inayofaa na matumizi ya mfuatano wa nasibu kweli. Mifano rahisi zaidi ya utegemezi huu ni misimbo ya mtiririko, ambayo mara nyingi hufanya kazi kwa kuacha au kutuma ujumbe wa maandishi wazi na matokeo ya PRNG, ikitoa maandishi ya siri. Kubuni PRNG zinazotosha kwa njia fiche ni ngumu sana kwani lazima zitimize vigezo vya ziada. Ukubwa wa kipindi chake ni kipengele muhimu katika ufaafu wa kriptografia wa PRNG, lakini sio pekee.
PRNG ya kompyuta ya awali iliyopendekezwa na John von Neumann mwaka wa 1946 inajulikana kama mbinu ya wastani ya mraba. Algorithm ni kama ifuatavyo: chukua nambari yoyote, iwe mraba, ondoa nambari za kati za nambari inayotokana kama "nambari nasibu", kisha utumie nambari hii kama nambari ya kuanzia kwa marudio yanayofuata. Kwa mfano, squaring nambari 1111 inatoa1234321, ambayo inaweza kuandikwa kama 01234321, nambari ya tarakimu 8 ni mraba wa nambari ya tarakimu 4. Hii inatoa 2343 kama nambari "ya nasibu". Matokeo ya kurudia utaratibu huu ni 4896, na kadhalika. Von Neumann alitumia nambari za tarakimu 10, lakini mchakato ulikuwa sawa.
Hasara za "mraba wa kati"
Tatizo la mbinu ya "mraba wa maana" ni kwamba mfuatano wote hatimaye unajirudia, baadhi kwa haraka sana, kwa mfano: 0000. Von Neumann alijua kuhusu hili, lakini alipata mbinu ya kutosha kwa madhumuni yake, na akawa na wasiwasi kwamba "marekebisho" ya hesabu yangeficha tu makosa badala ya kuyaondoa.
Von Neumann alipata jenereta za nambari za maunzi nasibu na za uwongo zisizofaa: ikiwa hazitarekodi matokeo yaliyotolewa, haziwezi kuangaliwa ili kubaini hitilafu baadaye. Ikiwa wangeandika matokeo yao, wangemaliza kumbukumbu ndogo ya kompyuta na hivyo uwezo wa kompyuta kusoma na kuandika nambari. Ikiwa nambari zingeandikwa kwenye kadi, zingechukua muda mrefu zaidi kuandika na kusoma. Kwenye kompyuta ya ENIAC aliyotumia, mbinu ya "mraba wa kati" na kutekeleza mchakato wa kupata nambari za uwongo za nasibu mara mia kadhaa zaidi ya kusoma nambari kutoka kwa kadi zilizopigwa.
Mraba wa wastani tangu wakati huo umechukuliwa na jenereta changamano zaidi.
Mbinu bunifu
Ubunifu wa hivi majuzi ni wa kuchanganya wastani wa mraba na mfuatano wa Weil. Njia hii inahakikisha bidhaa za ubora wa juu ndanimuda mrefu. Inasaidia kupata fomula bora za nambari za uwongo zisizo nasibu.
