Generador de nombres pseudoaleatoris
Un generador de nombres pseudoaleatoris (GPAN) és un algorisme que produeix una successió de nombres que és una molt bona aproximació a un conjunt aleatori de nombres. La successió no és exactament aleatòria en el sentit que queda completament determinada per un conjunt relativament petit de valors inicials, anomenats estat del GPAN. Si bé és possible generar successions mitjançant generadors de nombres aleatoris amb dispositius mecànics que són millors aproximacions a una successió aleatòria, els nombres pseudo-aleatoris són importants en la pràctica per a certes simulacions (per exemple, de sistemes físics mitjançant el mètode de Montecarlo), i exerceixen un paper central en la criptografia.
La majoria dels algorismes de generadors pseudoaleatorios produeixen successions que posseeixen una distribució uniforme segons diversos tipus de proves. Les classes més comunes d'aquests algorismes són generadors lineals congruents, generadors Fibonacci demorats, desplaçaments de registre amb retroalimentació lineal i desplaçaments de registre amb retroalimentació generalitzada. Entre els desenvolupaments més recents d'algorismes pseudoaleatoris s'hi troben el Blum Blum Shub, el Fortuna, i el Mersenne twister.
Es requereix una acurada anàlisi matemàtica per tenir algun tipus de confiança en què un dau GPAN genera nombres que són prou "aleatoris" com per ser útils per al propòsit per al qual hom els necessita. Robert R. Coveyou del Laboratori Nacional d'Oak Ridge va escriure un article titulat, "La generació de nombres aleatoris és massa important com per ser deixada a l'atzar."[1] com John von Neumann deia de broma, "Tothom qui desenvolupa mètodes aritmètics per produir dígits aleatoris està per descomptat en pecat."[2]
Problemes dels generadors determinístics modifica
A la pràctica, els resultats de molts GPAN presenten artefactes matemàtics que fan que els mateixos fallin en proves de detecció de paràmetres estadístics. Entre aquests s'inclouen,
- Períodes més curts que l'esperat per alguns estats llavor; en aquest context aquests estats llavor poden ser anomenats 'febles'
- Manca 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 diferent que la que correspon a una successió aleatòria
- Algunes seqüències de bits són 'més aleatòries' que altres
Els defectes que són exhibits pels GPAN van des d'un rang del que imperceptible fins l'absolutament obvi. L'algorisme de nombres aleatoris Randu utilitzat durant dècades en grans ordinadors tipus mainframe tenia serioses deficiències, i com a conseqüència molt del treball de recerca produït en aquest període és menys fiable del que podria haver estat.
Referències modifica
- ↑ Peterson, Ivars. The Jungles of Randomness: A Mathematical Safari. Wiley, NY, 1998. (Pp. 178) ISBN 0-471-16449-6
- ↑ "Various techniques used in connection with random digits", Applied Mathematics Sèries, no. 12, 36-38 (1951).
Bibliografia modifica
- 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 non-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 Programari , in Proc. 19th Annual Computer Security Applications Conference, Dec 2003.
- John von Neumann, "Various techniques used in connection with random digits," in AS Householder, G.E. Forsythe, and H.H. Germond, eds., Montecarlo Method , National Bureau of Standards Applied Mathematics Sèries, 12 (Washington, DC: US Government Printing Office, 1951): 36-38.
- NIST Recommendation for Random Number Generation Using deterministic Random Bit Generators Arxivat 2007-09-26 a Wayback Machine.
Enllaços externs modifica
- La biblioteca científica GNU. Una biblioteca lliure (GPL) en llenguatge C que inclou alguns algorismes GPAN.
- DieHarder: A free (GPL) C Random Number Test Suite.
- crng Arxivat 2011-12-27 a Wayback Machine.: Generadors aleatoris de nombres programats com a extensions de tipus Python codificades en llenguatge C.
- random.org Arxivat 2011-02-24 a Wayback Machine.: Web based Random-number generator built and maintained by Mads Haahr.
- http://eeyore.wu-wien.ac.at/src/ prng: Una col·lecció d'algorismes per generar nombres pseudoaleatorios programats en llenguatge C, sota GPL.
- Generating random numbers Generating random numbers[Enllaç no actiu] in Embedded Systems by Eric Uner
- Analysis of the Linux Random Number Generator by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman