Usuari:Mcapdevila/Generador de nombres pseudoaleatoris
Aquest article tenia importants deficiències de traducció i ha estat traslladat a l'espai d'usuari. Podeu millorar-lo i traslladar-lo altra vegada a l'espai principal quan s'hagin resolt aquestes mancances. Col·laboreu-hi! |
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 per 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 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çament de registres amb retroalimentació lineal i desplaçaments de registres amb retroalimentació generalitzada. Entre els desenvolupaments més recents d'algorismes pseudoaleatorios 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] I 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]
Vegeu també
[modifica]- Cadena de Markov
- Integració de Montecarlo
- Mètode quasi-Montecarlo
- Atzar
- Algorisme de Las Vegas
- Generador aleatori de nombres
- Estocàstic
Notes
[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).
Referències
[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
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: Generadors aleatoris de nombres programats com a extensions de tipus Python codificades en llenguatge C.
- random.org: Generador de nombres aleatoris al web, creat i mantingut per 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.
- Strange Attractors and TCP/IP Sequence Number Analysis - an analysis of the strength of PRNGs used to create TCP/IP sequence numbers by various operating systems using strange attractors. This is a good practical example of issues in PRNGs and the variation possible in their implementation.
- Strange Attractors and TCP/IP Sequence Number Analysis - One Year Later - a follow-up article demonstrating some of the evolution of various PRNG algorithms over time.
- Generating random numbers Generating random numbers in Embedded Systems by Eric Uner
- Analysis of the Linux Random Number Generator by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman