Generador de nombres pseudoaleatoris

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 comuns 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 de l'Oak Ridge National Laboratory 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 | modifica el codi]

Notes[modifica | modifica el codi]

  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).

Referències[modifica | modifica el codi]

  • 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 | modifica el codi]