Un nombre pseudoaleatori és un nombre especial generat per un generador especial. El Generador de bits aleatoris deterministes (PRNG), també conegut com a Generador de bits aleatoris deterministes (DRBG), és un algorisme per generar una seqüència de nombres les propietats dels quals s'aproximen a les característiques de les seqüències de nombres aleatoris. La seqüència de PRNG generada no és realment aleatòria, ja que està totalment determinada per un valor de llavor anomenat llavor de PRNG, que pot incloure valors realment aleatoris. Tot i que es poden generar seqüències més properes a l'atzar mitjançant generadors de nombres aleatoris de maquinari, els generadors de números pseudoaleatoris són importants a la pràctica per a la velocitat de generació de números i la seva reproductibilitat.
Aplicació
Els
PRNG són fonamentals per a aplicacions com ara la simulació (per exemple, per a Montecarlo), els jocs electrònics (per exemple, per a la generació de procediments) i la criptografia. Les aplicacions criptogràfiques requereixen que la sortidales dades no eren predictibles a partir d'informació anterior. Es requereixen algorismes més complexos que no heretin la linealitat dels PRNG simples.
Termes i condicions
Les bones propietats estadístiques són un requisit central per obtenir un PRNG. En general, cal una anàlisi matemàtica acurada per assegurar-se que el RNG genera nombres prou propers a l'atzar per ser adequats per a l'ús previst.
John von Neumann va advertir que no malinterpretar PRNG com un generador realment aleatori i va fer broma dient que "Qualsevol persona que consideri mètodes aritmètics per generar nombres aleatoris està sens dubte en un estat de pecat".
Utilitzar
PRNG es pot llançar des d'un estat inicial arbitrari. Sempre generarà la mateixa seqüència quan s'inicialitza amb aquest estat. El període PRNG es defineix de la següent manera: màxim sobre tots els estats inicials de la longitud del prefix de seqüència no repetida. El període està limitat pel nombre d'estats, normalment mesurats en bits. Com que la durada del període es duplica amb cada bit d'"estat" afegit, és fàcil crear PRNG amb períodes prou grans per a moltes aplicacions pràctiques.
Si l'estat intern del PRNG conté n bits, el seu període no pot ser superior a 2n resultats, és molt més curt. Per a alguns PRNG, la durada es pot calcular sense passar per alt tot el període. Els registres lineals de canvi de retroalimentació (LFSR) són normalmentes trien de manera que tinguin períodes iguals a 2n − 1.
Els generadors congruencials lineals tenen períodes que es poden calcular mitjançant factorització. Encara que el PPP repetirà els seus resultats després d'arribar al final del període, un resultat repetit no vol dir que s'hagi arribat al final del període, ja que el seu estat intern pot ser més gran que la sortida; això és especialment evident per als PRNG amb sortida d'un sol bit.
Possibles errors
Els errors trobats pels PRNG defectuosos van des de subtils (i desconeguts) fins a evidents. Un exemple és l'algoritme de nombres aleatoris RANDU, que s'ha utilitzat en sistemes centrals durant dècades. Va ser una deficiència greu, però la seva inadequació va passar desapercebuda durant un llarg període de temps.
En moltes àrees, els estudis de recerca que han utilitzat la selecció aleatòria, les simulacions de Montecarlo o altres mètodes basats en RNG són molt menys fiables del que podria ser el resultat d'un GNPG de mala qualitat. Fins i tot avui en dia, de vegades es requereix precaució, tal com demostra l'advertència de l'Enciclopèdia Internacional de Ciència Estadística (2010).
Estudi de cas d'èxit
Com a il·lustració, tingueu en compte el llenguatge de programació Java molt utilitzat. A partir del 2017, Java encara es basa en el generador lineal congruencial (LCG) per al seu PRNG.
Història
El primer PRNG per evitar problemes greus i encara córrer bastant ràpid,va ser el Mersenne Twister (que es comenta a continuació), que es va publicar el 1998. Des de llavors, s'han desenvolupat altres PRNG d' alta qualitat.
Però la història dels números pseudoaleatoris no s'acaba aquí. A la segona meitat del segle XX, la classe estàndard d'algorismes utilitzats per als PRNG incloïa generadors congruencials lineals. Se sabia que la qualitat del LCG era inadequada, però no hi havia millors mètodes disponibles. Press et al (2007) van descriure el resultat de la següent manera: "Si tots els articles científics els resultats dels quals estan en dubte a causa de [LCG i relacionats] desapareguessin dels prestatges de les biblioteques, hi hauria un buit de la mida del vostre puny a cada prestatge".
El principal assoliment en la creació de generadors pseudoaleatoris va ser la introducció de mètodes basats en recurrents lineals en un camp de dos elements; aquests oscil·ladors estan acoblats a registres de desplaçament de retroalimentació lineal. Van servir de base per a la invenció dels sensors de nombres pseudoaleatoris.
En particular, la invenció de 1997 de Mersen Twister va evitar molts dels problemes amb els generadors anteriors. El Mersenne Twister té un període de 219937−1 iteracions (≈4,3 × 106001). S'ha demostrat que es distribueix uniformement en (fins a) 623 dimensions (per a valors de 32 bits) i en el moment de la seva introducció era més ràpid que altres generadors estadísticament sòlids que produeixen seqüències de nombres pseudoaleatoris.
L'any 2003, George Marsaglia va introduir una família de generadors de desplaçament xor també basats en la repetició lineal. Aquests generadors són extremadamentsón ràpids i, combinats amb una operació no lineal, passen proves estadístiques rigoroses.
L'any 2006 es va desenvolupar la família de generadors WELL. Els generadors WELL milloren en certa manera la qualitat de Twister Mersenne, que té un espai d'estat massa gran i una recuperació molt lenta d'ells, generant números pseudoaleatoris amb molts zeros.
Criptografia
PRNG adequat per a aplicacions criptogràfiques s'anomena PRNG criptogràficament segur (CSPRNG). El requisit per a un CSPRNG és que un atacant que no conegui la llavor només té un avantatge marginal a l'hora de distingir la seqüència de sortida del generador d'una seqüència aleatòria. En altres paraules, mentre que un PRNG només és necessari per aprovar determinades proves estadístiques, un CSPRNG ha de superar totes les proves estadístiques que es limiten al temps polinomi en la mida de la llavor.
Tot i que la prova d'aquesta propietat està més enllà del nivell actual de la teoria de la complexitat computacional, es pot proporcionar una evidència sòlida reduint el CSPRNG a un problema que es considera difícil, com la factorització de nombres enters. En general, poden ser necessaris anys de revisió abans que un algorisme es pugui certificar com a CSPRNG.
S'ha demostrat que és probable que la NSA hagi inserit una porta posterior asimètrica al generador de números pseudoaleatori Dual_EC_DRBG certificat per NIST.
Algorismes pseudoaleatorisnúmeros
La majoria dels algorismes PRNG produeixen seqüències que es distribueixen uniformement per qualsevol de les diverses proves. Aquesta és una pregunta oberta. És un dels elements centrals en la teoria i la pràctica de la criptografia: hi ha alguna manera de distingir la sortida d'un PRNG d' alta qualitat d'una seqüència realment aleatòria? En aquest paràmetre, el resolutor sap que s'ha utilitzat un algorisme PRNG conegut (però no l'estat amb què s'ha inicialitzat), o bé s'ha utilitzat un algorisme realment aleatori. Ha de distingir-los.
La seguretat de la majoria d'algorismes i protocols criptogràfics que utilitzen PRNG es basa en el supòsit que és impossible distingir entre l'ús d'un PRNG adequat i l'ús d'una seqüència realment aleatòria. Els exemples més senzills d'aquesta dependència són els xifrats de flux, que sovint funcionen ometent o enviant el missatge de text sense format amb una sortida PRNG, produint el text xifrat. Dissenyar PRNG criptogràficament adequats és extremadament difícil, ja que han de complir criteris addicionals. La mida del seu període és un factor important en la idoneïtat criptogràfica d'un PRNG, però no l'únic.
Un primer PRNG d'ordinador proposat per John von Neumann el 1946 es coneix com el mètode dels quadrats mitjans. L'algorisme és el següent: agafeu qualsevol nombre, quadrat, traieu els dígits del mig del nombre resultant com a "número aleatori" i, a continuació, utilitzeu aquest nombre com a número inicial per a la següent iteració. Per exemple, quadrar el número 1111 dóna1234321, que es pot escriure com 01234321, un nombre de 8 dígits és el quadrat d'un nombre de 4 dígits. Això dóna 2343 com a nombre "atzar". El resultat de repetir aquest procediment és 4896, i així successivament. Von Neumann va utilitzar nombres de 10 dígits, però el procés va ser el mateix.
Inconvenients del "quadrat mitjà"
El problema amb el mètode del "quadrat mitjà" és que totes les seqüències es repeteixen, algunes molt ràpidament, per exemple: 0000. Von Neumann ho sabia, però va trobar un enfocament suficient per als seus propòsits i es va preocupar que el Les "correccions" matemàtiques només amagarien els errors en lloc d'eliminar-los.
Von Neumann ha trobat que els generadors de nombres aleatoris i pseudoaleatoris de maquinari no són adequats: si no enregistren la sortida generada, no es podran comprovar si hi ha errors més endavant. Si escriguessin els seus resultats, esgotarien la memòria disponible limitada de l'ordinador i, per tant, la capacitat de l'ordinador per llegir i escriure números. Si els números s'escriguessin a les targetes, trigarien molt més a escriure i llegir. A l'ordinador ENIAC va utilitzar el mètode del "quadrat mitjà" i va dur a terme el procés d'obtenir nombres pseudoaleatoris uns centenars de vegades més ràpid que llegir números de targetes perforades.
El quadrat mitjà ha estat substituït des de llavors per generadors més complexos.
Mètode innovador
Una innovació recent és combinar el quadrat mitjà amb la seqüència de Weil. Aquest mètode garanteix productes d' alta qualitat dinsllarg període. Ajuda a obtenir les millors fórmules de nombres pseudoaleatoris.
