Vikipedio:Projekto matematiko/Pseŭdohazarda nombra generilo

El Vikipedio

Ĉi tiu paĝo kreiĝis per aŭtomata tradukado el la angla lingvo. Ĝi ankoraŭ ne estas artikolo de la Vikipedio. Ĝia lingvaĵo montras stilajn, gramatikajn kaj strukturajn problemojn kaj bezonas plenan poluradon por esti skribata en akceptebla Esperanto. Post plena plibonigo movu la paĝon al Pseŭdohazarda nombra generilo (eble la nomo mem bezonas korekton) por igi ĝin artikolo de la Vikipedio. Se la ligo estas ruĝa, vi povas movi la paĝon. Se la ligo estas blua, jam ekzistas artikolo kun tiu titolo. Tiukaze necasas kunigi tiun artikolon kun la plibonigita versio de ĉi tiu paĝo.

pseŭdohazarda nombra generilo (_PRNG_) estas algoritmo (tiu, ke, kiu) (generas, naskas) vico de nombroj kiu estas ne vere hazarda. La (eligas, eligoj) de pseŭdohazardaj nombraj generiloj nur aproksimi iu de la propraĵoj de hazardaj nombroj. Kvankam vere hazardaj nombroj povas nur esti generitaj uzantaj aparataj hazardaj nombraj generiloj, pseŭda-hazarda nombroj estas grava en ĉifriko kaj por simulantaj fizikaj sistemoj kun la Montecarla maniero. Zorga analitiko estas postulita al certiĝi (tiu, ke, kiu) la algoritmo (generas, naskas) nombroj (tiu, ke, kiu) estas sufiĉe "hazarda"; kiel _Robert_ R. _Coveyou_ de Kverka Kresta Nacia Laboratorio iam titolis artikolo, "La generacio de hazardaj nombroj estas ankaŭ grava al esti (maldekstre, restita) al ŝanco."¹ John von NEUMANN emfazis ĉi tiu kun la mallaŭdo "Ĉiu kiu konsideras aritmetikaj manieroj de produktanta hazarda (ciferoj, ciferas) estas, kompreneble, en (ŝtato, stato, stati) de (peko, peki)."²

Plej pseŭda-hazarda (algoritmoj, algoritmas) produkti specimenoj (tiu, ke, kiu) estas unuforme distribuita. Komunaj klasoj de (algoritmoj, algoritmas) estas lineara _congruential_ (naskantoj, naskantas, generiloj, generas), _lagged_ Fibonacci (naskantoj, naskantas, generiloj, generas), linearaj retrokuplaj ŝovaj registroj kaj ĝeneraligis retrokuplo (ŝovi, ŝovo) (registras, reĝistroj, reĝistras). Ĵusa (aper(aĵ)oj, aper(aĵ)as) de (algoritmoj, algoritmas) inkluzivi _Blum_ _Blum_ _Shub_, _Fortuna_, kaj la Mersenne-a _twister_.

Enhavo 1 Imanenta _nonrandomness_ 2 Frua (manieroj, proksimiĝoj) 3 Mersenne-a _twister_ 4 Ĉifrike fiksi pseŭdohazardaj nombraj generiloj 5 Vidu ankaŭ jenon: 6 (Tononomoj, Notoj, Notas) 7 Referencoj 8 Ekstera (ligoj, ligas)

[redakti] Imanenta _nonrandomness_

Ĉar (ĉiu, iu) _PRNG_ kuri sur determina komputilo (kontrasta kvantuma komputilo) estas determina algoritmo, ĝia (eligi, eligo) estos _inevitably_ havi unu propraĵo (tiu, ke, kiu) vera hazarda vico devus ne eksponi: garantiita periodeco. Ĝi estas certa (tiu, ke, kiu) se la generilo uzas nur (fiksis, neŝanĝebligita) kvanto de memoro tiam, donita sufiĉa nombro de (ripetoj, ripetas), la generilo estos _revisit_ antaŭa interne (ŝtato, stato, stati), post kiu ĝi estos ripeti eterne. Generilo (tiu, ke, kiu) _isn_'t perioda povas esti (dizajnita, desegnita), sed ĝia memoro (postuloj, bezonoj, bezonas) devus kreski kiel ĝi _ran_. Aldone, _PRNG_ povas esti startita de ajna deirpunkto, aŭ (semo, vidis) (ŝtato, stato, stati), kaj estos ĉiam produkti identa vico de (tiu, ke, kiu) punkto sur. La praktika signifeco de ĉi tiu periodeco estas (limigita, limigis). La longo de la maksimumo (periodo, punkto) duobligas kun ĉiu malmulto de adiciis memoro. Ĝi estas facila al (masoni, ĉarpenti, konstrui) _PRNGs_ kun (periodoj, periodas, punktoj, punktas) ĝisrevido (tiu, ke, kiu) ne komputilo povis plenumi unu ciklo en la atendis vivperiodo de la universo. Ĝi estas (malfermi, malfermita) demando, kaj unu centralo al ĉifriko, ĉu estas (ĉiu, iu) vojo al (distingi, diferencigi) la (eligi, eligo) de bone-(dizajnita, desegnita) _PRNG_ de perfekta hazarda bruo sen scianta ĝia (semo, vidis). Plej ĉifriko fidas sur la supozo (tiu, ke, kiu) ĝi estas _infeasible_ al (distingi, diferencigi) taŭgi _PRNG_ de bruo; la plej simpla ekzemplo estas roja cifero, kiu (ofte) (laboroj, laboras) per prenante la ekskluziva ĉu de la sekreta mesaĝo kun la (eligi, eligo) de _PRNG_. La dizajno de tia _PRNGs_ estas ege malfacila, kaj plej programoj uzi multa pli simpla _PRNGs_.

En praktiko, multaj komuna _PRNGs_ eksponi _artifacts_ kiu povas kaŭzaj ilin al manki statistike gravaj testoj. Ĉi tiuj inkluzivi, sed estas certe ne (limigita, limigis) al:

• pli mallonga ol atendis (periodoj, periodas, punktoj, punktas) por iu (semo, vidis) ŝtatoj (ne plena (periodo, punkto))
• Malriĉa dimensia distribuo
• Sukcesa (valoroj, valoras) estas ne sendependa
• Iu (bitoj, bitas, enbuŝaĵoj, enbuŝaĵas, malmultoj, malmultas) estante 'pli hazarda' ol aliaj
• Manko de samformeco

Difektas eksponita per krevaĵis _PRNG_ (majo, povas) limigo de _unnoticeable_ al ridinda. La _RANDU_ hazarda nombra algoritmo uzita por jardekoj sur komputilegoj estis krevaĵita, kaj multa esplori laboro tiama estas malpli fidinda ol ĝi devus havi estas kiel rezulto. Iam, sed ne ĉiam, modelanta (problemoj, problemas) estas (rimarkita, avizita) kaj (plumbo, konduki) al (plibonigoj, plibonigas) en _PRNGs_.

[redakti] Frua (manieroj, proksimiĝoj)

La unua _PRNG_ estis sugestita per John von NEUMANN en (1946, Kategorio:1946), sciata kiel la mezo-kvadrata maniero. La maniero estis tre simpla: preni (ĉiu, iu) donita nombro, kvadrata ĝi, kaj forpreni la mezo (ciferoj, ciferas) de la rezultanta nombro kiel via "hazarda nombro" kaj la (semo, vidis) por via venonta operacio. Ekzemple, (kvadratanta, placanta, kvadratiganta) la nombro "1111" devus rezulto en "1234321", kiu povus esti skribita kiel "01234321", 8-cifera nombro estante la kvadrato de 4-cifera nombro, provizanta "2343" kiel la "hazarda" nombro. Ripetanta procezo devus doni vi "4896" kiel la venonta rezulto, kaj tiel plu. _Von_ Neumann-aj uzitaj nombroj de 10 (ciferoj, ciferas) en longo, sed la procezo estis la sama.

La problemo kun la "meza kvadrato" maniero estas (tiu, ke, kiu) (ebena, para, eĉ) la plej bona (vicoj, vicas) devas eble ripeti sin, iu farante (do, tiel) tre rapide. Iu (vicoj, vicas), kiel "0000", estos detrui la procezo (tuj, senpere). _Von_ Neumann-a estis konscia de tiaj aĵoj, sed por lia (celoj, celas) li fundamenti ĝi sufiĉa kaj ĝiaj eraroj facila al detekti (li estis (ĝenita, zorgita) (tiu, ke, kiu) matematika "_fixes_" devus simple kaŝi la eraroj iom ol forigi ilin). Sur la _ENIAC_ komputila kiu li estis uzanta, uzanta la "meza kvadrato" manieraj generitaj nombroj je kurzo iu ducent (tempoj, tempas) pli rapide ol legantaj nombroj de punĉo (kartoj, kartas, diskombas). En _Von_ Neumann-a's vido, aparataj hazardaj nombraj generiloj devus ne laboro, ĉar se ili farita ne rikordo la nombroj generita, ili povis ne poste esti testita por eraroj. Se ilia faritaj rikordaj iliaj nombroj, ili devus imposto la komputila memoro kaj ĝia ebleco al legi kaj skribi nombroj. Se la nombroj estis skribita al (kartoj, kartas, diskombas), ili devus preni ankaŭ longa al legi. La mezo-kvadrata maniero estis simpla kaj laboris por lia (celoj, celas), sed poste aplikoj de la Montecarla maniero devus postuli pli ellabori (naskantoj, naskantas, generiloj, generas).

[redakti] Mersenne-a _twister_

La ĵusa (invento, inventaĵo) de la Mersenne-a _twister_ algoritmo, per _Makoto_ Macumoto kaj _Takuji_ _Nishimura_ en (1997, Kategorio:1997), evitas la plejparto de ĉi tiuj (problemoj, problemas). Ĝi havas kolosa (periodo, punkto) de 2¹⁹⁹³⁷-1 (ripetoj, ripetas) ((kredeble, verŝajne) pli ol la nombro de (kalkuladoj, kalkuladas, komputoj, komputas) kiu povas esti (aperita, plenumita) en la estonta ekzisto de la universo), estas pruvita al esti _equidistributed_ en 623 (dimensioj, dimensias) (por 32-malmulto (valoroj, valoras)), kaj (kuras, rulas) pli rapida ol ĉiuj sed la plej malgranda statistike dezirinda (naskantoj, naskantas, generiloj, generas). Ĝi estas nun (kreskante, pligrandiĝante) (fariĝanta, iĝanta, iĝante) la "hazarda nombra generilo de elekto" por statistika (simuladoj, simuladas) kaj genera modelanta.

Tamen, ĝi estas ebla al kompetente analizi la (eligi, eligo) de la Mersenne-a _Twister_ kaj agnoski la nombroj kiel estante ne-hazarda (kiel kun la _Berlekamp_-_Massey_ algoritmo aŭ vastigaĵo de ĝi, kiel la (Kano, Anĉo)-_Sloane_ algoritmo). Je ĉi tiu tempo ĉi tiu havas ne sciata negativa efikas escepti farante la Mersenne-a _Twister_ _unusable_ kiel ĉifrike fiksi _PRNG_.

[redakti] Ĉifrike fiksi pseŭdohazardaj nombraj generiloj

Majno (rivero) artikolo: Ĉifrike fiksi pseŭdo-hazarda nombra generilo

_PRNG_ taŭgi por ĉifrikaj aplikoj estas (nomita, vokis) ĉifrike fiksi _PRNG_ (_CSPRNG_). La diferenco inter _PRNG_ kaj _CSPRNG_ povas esti sumita supren simple: _CSPRNG_ devus aperi nediferencigebla de hazarda al (ĉiu, iu) algoritmo, (dum, ĉar) normale _PRNG_ estas nur postulis al aperi hazarda al normaj statistikaj testoj.

Iuj klasoj de _CSPRNGs_ inkluzivi jeno:

• Rojo (ciferoj, ciferas) aŭ (bari, bloko) (ciferoj, ciferas) (kuro, kurante, rulante) en nombrilo aŭ (eligi, eligo) retrokupla reĝimo.
• Speciala (dezajnoj, dezajnas, dizajnas, projektas, dizajnoj, desegnas) kun (garantiaĵo, sekureco) pruvo. Ekzemple _Blum_ _Blum_ _Shub_ havas forta kondiĉa (garantiaĵo, sekureco) pruvo, kvankam ĝi estas malfrua.
• _PRNGs_ (tiu, ke, kiu) havi estas (dizajnita, desegnita) aparte al esti ĉifrike fiksi. Unu ekzemplo estas _ISAAC_, kiu estas rapida kaj kies (garantiaĵo, sekureco) kandidatiga esprimilo, interalie, tre granda atendis cikla tempo.

[redakti] Vidu ankaŭ jenon:

• Pseŭdo-hazarda duuma vico
• Hazardigita algoritmo
• Hazarda nombra generilo
• Hazarda nombra generilo ataki
• Listo de kvazaŭhazardaj nombraj generiloj
• Aparata hazarda nombra generilo
• Hazardo

[redakti] (Tononomoj, Notoj, Notas)

¹ _Peterson_. _Ivars_. La (Ĝangaloj, Ĝangalas) de Hazardo: A Matematika _Safari_. _Wiley_, _NY_, (1998, Kategorio:1998). (_pp_. 178) ISBN 0-471-16449-6

² "Diversaj teknikoj uzita en ligo kun hazarda (ciferoj, ciferas)", Aplikita Matematika Serio, ne. 12, 36-38 ((1951, Kategorio:1951)).

[redakti] Referencoj

• Donald KNUTH. La Arto de Komputila Programado, Volumeno 2: _Seminumerical_ (Algoritmoj, Algoritmas), Tria Redakcio. Addison-a-_Wesley_, (1997, Kategorio:1997). ISBN 0-201-89684-2. Ĉapitro 3, _pp_.1–193.
• J. _Viega_, Praktika Hazarda Nombra Generacio en Programaro, en _Proc_. 19-a Ĉiujara Komputilo (Garantiaĵo, Sekureco) Aplika Konferenco, _Dec_. (2003, Kategorio:2003).
• John von NEUMANN, "Diversaj teknikoj uzita en ligo kun hazarda (ciferoj, ciferas)," en A.S. Majstro, G.E. _Forsythe_, kaj H.H. _Germond_, _eds_., Montecarla Maniero, Nacia Buroo de (Normoj, Normas) Aplikita Matematika Serio, 12 (Vaŝingtono: U.S. Registaro (Presanta, Printanta) Oficejo, (1951, Kategorio:1951)): 36-38.

[redakti] Ekstera (ligoj, ligas)

• La GNU Scienca Biblioteko. Libera (_GPL_) C biblioteko (tiu, ke, kiu) inkluzivas nombro de _PRNG_ (algoritmoj, algoritmas).
• _DieHarder_: A libera (_GPL_) C Hazarda Nombra Prova Suito.
• _crng_: Hazarda-nombro (naskantoj, naskantas, generiloj, generas) (_RNGs_) realigis kiel Pitona vastigaĵo (klavas, tipoj) (kodis, moruita) en C.
• http://eeyore.wu-wien.ac.at/src/ _prng_: A kolekto de (algoritmoj, algoritmas) por generante pseŭdohazardaj nombroj kiel biblioteko de C funkcioj, malpremis sub la _GPL_.
• (Fremda, Stranga) (Altenaĵoj, Altenaĵas) kaj _TCP_/_IP_ Vica Nombra Analitiko - analitiko de la forteco de _PRNGs_ kutima krei _TCP_/_IP_ vicaj nombroj per diversaj (operaciumoj, mastrumaj sistemoj) uzanta (fremda, stranga) (altenaĵoj, altenaĵas). Ĉi tiu estas bona praktika ekzemplo de (eldonas, aferoj) en _PRNGs_ kaj la variacio ebla en ilia realigo.
  • (Fremda, Stranga) (Altenaĵoj, Altenaĵas) kaj _TCP_/_IP_ Vica Nombra Analitiko - Unu Jaro Poste - postoperacia kuracada artikolo _demonsrating_ iu de la evoluismo de diversaj _PRNG_ (algoritmoj, algoritmas) super tempo.