Anar al contingut

Generador de números pseudoaleatorios

De L'Enciclopèdia, la wikipedia en valencià

Un generador de números pseudoaleatorios (GNPA) és un algoritme que produïx una successió de números que és una molt bona aproximació a un conjunt aleatori de números. La successió no és exactament aleatòria en el sentit de que queda completament determinada per un conjunt relativament chicotet de valors inicials, cridats el estat de el GNPA. Si be és possible generar successions per mig de generadors de números aleatoris per dispositius mecànics que són millors aproximacions a una successió aleatòria, els números pseudoaleatorios són importants en la pràctica per a simulacions (per eixemple, de sistemes físics per mig del método de Montecarlo), i eixerciten un paper central en la criptografia.

La majoria dels algoritmes de generadors pseudoaleatorios produïxen seqüències que presenten una distribució uniforme conforme a diversos tipos de proves estadístiques.

Entre les classes més comunes d'estos algoritmes es troben els generadors llineals congruenciales, els generadors Fibonacci demorats, els basats en registres de desplaçament en retroalimentación llineal (LFSR) i aquells en retroalimentación generalisada.

Entre els desenrolls més recents de generadors pseudoaleatorios destaquen els algoritmes Blum Blum Shub, Fortuna i el Mersenne twister, àmpliament utilisats per la seua calitat estadística i la seua aplicabilidad en criptografia, simulació i modelació computacional.

Es requerix d'un cuidadós anàlisis matemàtic per a tindre algun tipo de confiança en que un dau GPAN genera números que són suficientment "aleatoris" per a ser útils per al propòsit per al que li'ls precisa. Robert R. Coveyou del Oak Ridge National Laboratory va escriure un artícul titulat «La generació de números aleatoris és massa important com per a ser deixat a l'encert».[1] I com John von Neumann dia en broma, «tot el que desenrolla métodos aritmètics per a produir dígits aleatoris esta des de després en pecat».[2]

Problemes dels generadors determinista

[editar | editar còdic]

En la pràctica, els resultats de molts GNPA presenten artefactes matemàtics que fan que els mateixos fallen en proves de detecció de paràmetros estadístics. Entre estos s'inclouen:

  • Periodos més curts que lo esperat per a alguns estats llavor; en este context dits estats llavor poden ser cridats 'dèbils'
  • Falta d'uniformitat de la distribució
  • Correlació de valors successius
  • Pobre distribució dimensional de la successió resultat
  • Les distàncies entre l'ocurrència de certs valors estan distribuïdes de manera distinta que la que correspon a una successió aleatòria
  • Algunes seqüències de bits són 'més aleatòries' que unes atres

Els defectes que són exhibits pels GNPA van des d'un ranc de lo imperceptible fins a lo absolutament obvi. L'algoritme de números aleatoris RANDU utilisat per décades en grans computadores tipo mainframe posseïa séries deficiències, i com a conseqüència molt del treball d'investigació produït en eixe periodo és menys confiable de lo que podria haver segut.

Llista de Generadors de Números Pseudoaleatorios

[editar | editar còdic]

En esta secció es presenta una llista de generadors que varen marcar històricament el camp d'estudi del procés de generació de números pseudoaleatorios, ya siga per la seua importància històrica o per ser un model innovador tenint en conte les seues respectives époques. Ademés, a pesar de ser PRNGs (Generadors de Números Pseudoaleatorios, en anglés) alguns d'ells poden ser aplicables dins del camp de la criptografia, com és el cas del fort algoritme Blum Blum Shub i Fortuna com s'ha presentat anteriorment.

Algoritme Any Autors Referències Descripció
Mig del quadrat 1946 John von Neumann [3] Un PRNG considerat de baixa calitat pero de gran rellevància històrica per ser un dels algoritmes pioners.
Generador de Lehmer 1951 D. H. Lehmer [4] També conegut com a método Congruent Llineal Multiplicativo i de gran influència en este camp d'estudi.
Generador llineal congruencial 1958 W. E. Thomson [5] Model derivat de Lehmer (1951) de gran influència i molt estudiat en tot lo món.
Generador Lagged Fibonacci (LFG) 1958 G. J. Mitchell; D.P. Moore [6] Un algoritme molt influent en el camp de l'estudi dels processos de generació de números aleatoris que va inspirar a atres grans autors en els següents anys com George Marsaglia, creador del valorat test de calitat de números aleatoris cridat "Diehard", per eixemple.
Linear-feedback Shift Register 1965 R. C. Tausworthe [7] Un generador el disseny del qual va influir en molts atres PRNG posteriors. Per lo tant, és molt important des del punt de vista històric. També conegut com el generador Tausworthe.
Generador de Wichmann-Hill 1982 B. A. Wichmann; D. I. Hill [8] Una combinació de tres menuts LCGs, adequats per a CPUs de 16 bits. Àmpliament utilisat en molts programes, per eixemple es va utilisar en Excel 2003 i algunes versions posteriors per a la funció RAND de Excel i va anar el generador per defecte en el llenguage Python fins a la versió 2.2.
Rule 30 1983 Stephen Wolfram [9] Generador basat en autómates celulars.
Blum Blum Shub 1986 Manuel Blum;Leonore Blum; Michael Shub [10] Considerat un dels generadors més segurs des del punt de vista criptográfico, degut principalment a l'implementació en la seua fòrmula d'estudis i conceptes derivats de la teoria de números.
Generador de Park-Miller 1988 S. K. Park; K. W. Miller [11] Una implementació específica d'un generador de Lehmer, àmpliament utilisada perque s'inclou en C++ com la funció minstd_rand0 a partir de C++11.
MIXMAX 1991 G. K. Savvidy; N. G. Ter-Arutyunyan-Savvidy [12] És un generador que pertany a la classe de generador llineal congruent matricial, una generalisació del Método Congruent Llineal. La llògica de la família de generadors MIXMAX es basa en els resultats de la teoria ergòdica i la mecànica clàssica.
Add-with-carry (ACW) 1991 G. Marsaglia; A. Zaman [13] Una modificació dels generadors Lagged-Fibonacci.
Subtract-with-borrow 1991 G. Marsaglia; A. Zaman [13] Algoritme derivat dels generadors Lagged-Fibonacci.
ISAAC 1993 R. J. Jenkins [14] Generador criptográfico segur (CSPRNG) desenrollat per Robert J. Jenkins.
Mersenne twister 1998 M. Matsumoto; T. Nishimura [15] Provablement siga el generador més conegut d'esta llista, principalment perque és un algoritme implementat en les funcions RAND dels llenguages de programació Python i R, ademés de la seua gran presència en jocs electrònics com el Pro Evolution Soccer (PES).
Xorshift 2003 G. Marsaglia [16] És un subtipo molt ràpit de generadors LFSR. Marsaglia també va propondre com a millora el generador xorwow, en el que l'eixida d'un generador xorshift se sumixca en una seqüència de Weyl. El generador xorwow és el generador per defecte de la biblioteca CURAND de l'interfaç de programació d'aplicacions nVidia CUDA per a unitats de processament gràfic.
Fortuna 2003 Bruce Schneier; Niels Ferguson Algoritme considerat criptográficamente segur. Un CSPRNG molt conegut per ser implementat en els sistemes i productes d'Apple.
Well equidistributed long-period linear (WELL) 2006 F. Panneton; P. L'Ecuyer; M. Matsumoto [17] Algoritme conegut per ser complementari al Mersenne Twister (MT), buscant deliberadament cobrir els seus punts dèbils.
Advanced Randomization System (ARS) 2011 J. Salmon; M. Moraes; R. Dror; D. Shaw [18] Una versió simplificada del sifrat en bloc AES, que permet un rendiment molt ràpit en el sistema que soporta AES-NI.
Permuted Congruential Generator (PCG) 2014 M. E. O'Neill [19] Un model derivat del Método Llineal Congruencial.
Random Cycle Bit Generator (RCB) 2016 R. Cookman [20] El RCB es descriu com un generador de patrons de bits fet per a superar algunes de les deficiències en el Mersenne Twister (MT) i la restricció de duració de periodo/bit curt dels generadors de desplaçament/mòdul.
Xoroshiro128+ 2018 D. Blackman; S. Vigna [21] Una modificació dels generadors Xorshift de G. Marsaglia, un dels generadors més ràpits en les CPUs modernes de 64 bits. Els generadors relacionats són xoroshiro128**, xoshiro256+ i xoshiro256***.
64-bit MELG (MELG-64) 2018 S. Harase; T. Kimoto [22] Una implementació de generadors llineals F2 de 64 bits en el periodo primari de Mersenne.
Squares RNG 2020 B. Widynski [23] Generador derivat del método del quadrat mig propost per Jhon von Neumman.
Itamaracá (Ita) 2021 D. H. Pereira [24] Conegut per ser el primer algoritme PRNG que té la Funció de Valor Absolut en la seua base. Itamaracá també es presenta com un model senzill i ràpit que genera seqüències de números aleatoris aperiódicos.

Notes

[editar | editar còdic]
  1. ↑ Peterson, Ivars. The Jungles of Randomness: A Mathematical Safari. Wiley, NY, 1998. (pp. 178) ISBN 0-471-16449-6
  2. ↑ "Various techniques used in connection with random digits", Applied Mathematics Séries, no. 12, 36-38 (1951).
  3. ↑ National Institute of Standards and Technology.Consultat el 2022-05-12.
  4. ↑ Mathematical Tables and Other Aids to Computation.2(18)
    229.ISSN 0891-6837.doi:10.2307/2002294.Consultat el 2022-05-12.
  5. ↑ «Validate User». academic.oup.com. doi:10.1093/comjnl/1.2.83. Consultat el 2022-05-12.
  6. ↑ Mathematics of Computation.24(110)
    504.ISSN 0025-5718.doi:10.1090/S0025-5718-1970-0400642-2.Consultat el 2022-05-12.
  7. ↑ Mathematics of Computation.19(90)
    201–209.ISSN 0025-5718.doi:10.1090/S0025-5718-1965-0184406-1.Consultat el 2022-05-12.
  8. ↑ Journal of the Royal Statistical Society. Séries C (Applied Statistics).31(2)
    188–190.ISSN 0035-9254.doi:10.2307/2347988.Consultat el 2022-05-12.
  9. ↑ Reviews of Modern Physics.55(3)
    601–644.doi:10.1103/RevModPhys.55.601.Consultat el 2022-05-12.
  10. ↑ SIAM Journal on Computing.15(2)
    364–383.ISSN 0097-5397.doi:10.1137/0215025.Consultat el 2022-05-12.
  11. ↑ Communications of the ACM.31(10)
    1192–1201.ISSN 0001-0782.doi:10.1145/63039.63042.Consultat el 2022-05-12.
  12. ↑ Journal of Computational Physics.97(2)
    566–572.ISSN 0021-9991.doi:10.1016/0021-9991(91)90015-D.Consultat el 2022-05-12.
  13. ↑ 13,0 13,1 The Annals of Applied Probability.1(3)
    462–480.ISSN 1050-5164.doi:10.1214/aoap/1177005878.Consultat el 2022-05-12.
  14. ↑ «burtleburtleburtleburtleburtle». www.burtleburtle.net. Consultat el 2022-05-12.
  15. ↑ ACM Transactions on Modeling and Computer Simulation.8(1)
    3–30.ISSN 1049-3301.doi:10.1145/272991.272995.Consultat el 2022-05-12.
  16. ↑ Journal of Statistical Software.8
    1–6.ISSN 1548-7660.doi:10.18637/jss.v008.i14.Consultat el 2022-05-12.
  17. ↑ ACM Transactions on Mathematical Software.32(1)
    1–16.ISSN 0098-3500.doi:10.1145/1132973.1132974.Consultat el 2022-05-12.
  18. ↑ Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis.Association for Computing Machinery.
    1–12.doi:10.1145/2063384.2063405.Consultat el 2022-05-12.
  19. ↑ IEEE SENSORS 2014 Proceedings.IEEE.doi:10.1109/icsens.2014.6985457.Consultat el 2022-05-12.
  20. ↑ SpringerReference.Springer-Verlag.Consultat el 2022-05-12.
  21. ↑ arXiv:1805.01407 [cs].Consultat el 2022-05-12.
  22. ↑ ACM Transactions on Mathematical Software.44(3)
    30:1–30:11.ISSN 0098-3500.doi:10.1145/3159444.Consultat el 2022-05-12.
  23. ↑ arXiv:2004.06278 [cs].Consultat el 2022-05-12.
  24. ↑ doi:10.33774/coe-2022-zsw6t.Consultat el 2022-05-12.

Referències

[editar | editar còdic]
  • Michael Luby, Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. A definitive source of techniques for provably random sequences.
  • Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3, pp. 1–193. Extensive coverage of statistical tests for senar-randomness.
  • R. Matthews Maximally Periodic Reciprocals Bulletin of the Institute of Mathematics and its Applications 28 147-148 1992
  • J. Viega, Practical Random Number Generation in Software, in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.
  • John von Neumann, "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Montecarlo Method, National Bureau of Standards Applied Mathematics Séries, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.
  • NIST Recommendation for Random Number Generation Using Deterministic Random Bit Generators


Referències

[editar | editar còdic]


Obtingut de «https://www.lenciclopedia.org/w/index.php?title=Generador_de_números_pseudoaleatorios&oldid=829362»