Ett pseudo-slumptal är ett speciellt nummer som genereras av en speciell generator. Deterministic Random Bit Generator (PRNG), även känd som Deterministic Random Bit Generator (DRBG), är en algoritm för att generera en sekvens av tal vars egenskaper approximerar egenskaperna hos slumptalssekvenser. Den genererade PRNG-sekvensen är inte riktigt slumpmässig, eftersom den helt och hållet bestäms av ett frövärde som kallas PRNG-frö, vilket kan innehålla verkligt slumpmässiga värden. Även om sekvenser som är närmare slumpmässiga kan genereras med hjälp av hårdvarugeneratorer för slumptal, är pseudo-slumptalsgeneratorer viktiga i praktiken för hastigheten på talgenerering och deras reproducerbarhet.
Application
PRNGs är centrala för applikationer som simulering (t.ex. för Monte Carlo), elektroniska spel (t.ex. för procedurgenerering) och kryptografi. Kryptografiska applikationer kräver att utdatauppgifterna var inte förutsägbara från tidigare information. Mer komplexa algoritmer krävs som inte ärver linjäriteten hos enkla PRNG:er.
Användarvillkor
Bra statistiska egenskaper är ett centr alt krav för att erhålla en PRNG. I allmänhet behövs noggrann matematisk analys för att vara säker på att RNG genererar tal som är tillräckligt nära slumpmässiga för att vara lämpliga för den avsedda användningen.
John von Neumann varnade för att misstolka PRNG som en verkligt slumpgenerator och skämtade om att "Alla som överväger aritmetiska metoder för att generera slumpmässiga tal är verkligen i ett tillstånd av synd."
Använd
PRNG kan startas från ett godtyckligt initi altillstånd. Den kommer alltid att generera samma sekvens när den initieras med detta tillstånd. PRNG-perioden definieras enligt följande: maximum över alla initiala tillstånd av längden av det icke-repeterande sekvensprefixet. Perioden begränsas av antalet tillstånd, vanligtvis mätt i bitar. Eftersom periodlängden potentiellt fördubblas med varje "tillstånds"-bit som läggs till, är det lätt att skapa PRNG:er med perioder som är tillräckligt stora för många praktiska tillämpningar.
Om det interna tillståndet för PRNG innehåller n bitar kan dess period inte vara mer än 2n resultat, den är mycket kortare. För vissa PRNG:er kan varaktigheten beräknas utan att förbigå hela perioden. Linjära återkopplingsskiftregister (LFSR) är typisktväljs så att de har perioder lika med 2n − 1.
Linjära kongruentialgeneratorer har perioder som kan beräknas med hjälp av factoring. Även om PPP kommer att upprepa sina resultat efter att de når slutet av perioden, betyder ett upprepat resultat inte att slutet av perioden har uppnåtts, eftersom dess interna tillstånd kan vara större än output; detta är särskilt uppenbart för PRNG:er med enbitsutgång.
Möjliga fel
Fel som hittats av defekta PRNG:er sträcker sig från subtila (och okända) till uppenbara. Ett exempel är RANDU-slumptalsalgoritmen, som har använts på stordatorer i decennier. Det var en allvarlig brist, men dess otillräcklighet gick obemärkt förbi under lång tid.
Inom många områden är forskningsstudier som har använt slumpmässigt urval, Monte Carlo-simuleringar eller andra metoder baserade på RNG mycket mindre tillförlitliga än vad som kan vara resultatet av GNPG av dålig kvalitet. Även idag krävs ibland försiktighet, vilket framgår av varningen i International Encyclopedia of Statistical Science (2010).
Lyckad fallstudie
Som en illustration, betrakta det flitigt använda programmeringsspråket Java. Från och med 2017 är Java fortfarande beroende av Linear Congruential Generator (LCG) för sin PRNG.
Historia
Den första PRNG för att undvika allvarliga problem och fortfarande köra ganska snabbt,var Mersenne Twister (diskuteras nedan), som publicerades 1998. Sedan dess har andra högkvalitativa PRNG:er utvecklats.
Men historien om pseudoslumptal slutar inte där. Under andra hälften av 1900-talet inkluderade standardklassen av algoritmer som användes för PRNG:er linjära kongruentialgeneratorer. Kvaliteten på LCG var känd för att vara otillräcklig, men bättre metoder fanns inte tillgängliga. Press et al (2007) beskrev resultatet på följande sätt: "Om alla vetenskapliga artiklar vars resultat är tveksamma på grund av [LCG och relaterade] försvann från bibliotekshyllorna, skulle det finnas en lucka lika stor som din knytnäve på varje hylla."
Huvudprestationen i skapandet av pseudo-slumpgeneratorer var introduktionen av metoder baserade på linjärt återkommande i ett tvåelementsfält; sådana oscillatorer är kopplade till linjära återkopplingsskiftregister. De fungerade som grunden för uppfinningen av sensorer för pseudo-slumptal.
Särskilt 1997 års uppfinning av Mersen Twister undvek många av problemen med tidigare generatorer. Mersenne Twister har en period på 219937−1 iterationer (≈4,3 × 106001). Det har visat sig vara likformigt fördelat i (upp till) 623 dimensioner (för 32-bitars värden), och var vid tiden för dess introduktion snabbare än andra statistiskt sunda generatorer som producerar pseudoslumptalssekvenser.
År 2003 introducerade George Marsaglia en familj av xorshift-generatorer också baserade på linjär upprepning. Dessa generatorer är extremtär snabba och - i kombination med en icke-linjär operation - klarar de rigorösa statistiska tester.
Under 2006 utvecklades WELL-generatorfamiljen. WELL-generatorer förbättrar på sätt och vis kvaliteten på Twister Mersenne, som har ett alltför stort tillståndsutrymme och mycket långsam återhämtning från dem, och genererar pseudoslumptal med många nollor.
Kryptografi
PRNG lämplig för kryptografiska applikationer kallas kryptografiskt säker PRNG (CSPRNG). Kravet för en CSPRNG är att en angripare som inte känner till fröet endast har en marginell fördel i att skilja generatorns utdatasekvens från en slumpmässig sekvens. Med andra ord, medan en PRNG bara krävs för att klara vissa statistiska test, måste en CSPRNG klara alla statistiska test som är begränsade till polynomtid i fröstorlek.
Även om beviset för denna egenskap ligger utanför den nuvarande nivån av beräkningskomplexitetsteori, kan starka bevis tillhandahållas genom att reducera CSPRNG till ett problem som anses vara svårt, som heltalsfaktorisering. I allmänhet kan det krävas flera års granskning innan en algoritm kan certifieras som en CSPRNG.
Det har visat sig att det är troligt att NSA satte in en asymmetrisk bakdörr i den NIST-certifierade Dual_EC_DRBG pseudo-slumptalsgeneratorn.
Pseudo-slumpmässiga algoritmernummer
De flesta PRNG-algoritmer producerar sekvenser som är jämnt fördelade av något av flera tester. Detta är en öppen fråga. Det är en av de centrala i teorin och praktiken av kryptografi: finns det ett sätt att skilja produktionen av en högkvalitativ PRNG från en verkligt slumpmässig sekvens? I den här inställningen vet resolvern att antingen en känd PRNG-algoritm användes (men inte tillståndet den initierades med), eller så användes en verkligt slumpmässig algoritm. Han måste skilja mellan dem.
Säkerheten för de flesta kryptografiska algoritmer och protokoll som använder PRNG:er är baserad på antagandet att det är omöjligt att skilja mellan användningen av en lämplig PRNG och användningen av en verkligt slumpmässig sekvens. De enklaste exemplen på detta beroende är strömchiffer, som oftast fungerar genom att utelämna eller skicka klartextmeddelandet med en PRNG-utgång, vilket producerar chiffertexten. Att designa kryptografiskt lämpliga PRNG:er är extremt svårt eftersom de måste uppfylla ytterligare kriterier. Storleken på dess period är en viktig faktor för den kryptografiska lämpligheten för en PRNG, men inte den enda.
En tidig dator-PRNG som föreslogs av John von Neumann 1946 är känd som medelkvadratmetoden. Algoritmen är som följer: ta valfritt tal, kvadrera det, ta bort mittsiffrorna i det resulterande talet som ett "slumptal", använd sedan detta nummer som startnummer för nästa iteration. Till exempel ger talet 1111 i kvadrat1234321, som kan skrivas som 01234321, är ett 8-siffrigt tal kvadraten på ett 4-siffrigt tal. Detta ger 2343 som ett "slumpmässigt" tal. Resultatet av att upprepa denna procedur är 4896, och så vidare. Von Neumann använde tiosiffriga nummer, men processen var densamma.
Nackdelar med "mitttorget"
Problemet med "mean square"-metoden är att alla sekvenser så småningom upprepas, vissa mycket snabbt, till exempel: 0000. Von Neumann visste om detta, men han fann ett tillvägagångssätt som var tillräckligt för sina syften, och var orolig för att matematiska "korrigeringar" skulle bara dölja felen istället för att ta bort dem.
Von Neumann fann slumpmässiga och pseudoslumptalsgeneratorer för hårdvara som olämpliga: om de inte registrerar den genererade utdata kan de inte kontrolleras för fel senare. Om de skulle skriva ner sina resultat skulle de tömma datorns begränsade tillgängliga minne och därmed datorns förmåga att läsa och skriva siffror. Om siffror skrevs på kort skulle de ta mycket längre tid att skriva och läsa. På ENIAC-datorn använde han metoden "mellanruta" och utförde processen att erhålla pseudoslumptal flera hundra gånger snabbare än att läsa siffror från hålkort.
Mean square har sedan dess ersatts av mer komplexa generatorer.
Innovativ metod
En ny innovation är att kombinera medelkvadraten med Weil-sekvensen. Denna metod säkerställer högkvalitativa produkter inomlång period. Det hjälper att få de bästa formlerna för pseudo-slumptal.
