Pseudoslumptalsgenerator
Från Rilpedia
En pseudoslumptalsgenerator är en algoritm för att producera en skenbart slumpmässig serie tal. Med pseudo åsyftas det faktum att en algoritm nödvändigtvis är deterministisk, det vill säga i princip förutsägbar. "Sanna" slumptal, av den typ som enligt rådande uppfattning om fysikens lagar kan produceras av en hårdvarubaserad slumptalsgenerator (exempelvis genom tärningskast), kan därför inte genereras av en algoritm. Däremot är det möjligt att på algoritmisk väg producera tal som är "tillräckligt slumpmässiga" för så gott som alla praktiska syften. Slumptal används av många olika typer av programvara, exempelvis inom kryptografi, Monte Carlo-algoritmer, vetenskapliga simuleringar, och datorspel.
Innehåll |
Modell
En pseudoslumptalsgenerator beskrivs av ett tillstånd S som är osynligt för omvärlden, en funktion f som producerar det tal f(S) som ska matas ut, och en funktion g som vid varje utmatning ersätter tillståndet S med g(S). Det utmatade värdet kan vara en enstaka bit eller ett tal med ett fåtal bitar, exempelvis med ett processorregisters storlek.
Om implementationen bara har tillgång till en begränsad mängd minne, vilket är fallet för alla program som körs på fysiska datorer, kan S bara anta ett ändligt antal olika värden. Som följd kommer varje pseudoslumptalssekvens till slut att börja upprepa sig. Antalet tal som kan produceras innan så sker kallas för slumptalsgeneratorns period. Om S representeras av ett n-bitars binärt tal, vilket oftast är fallet i praktiken, är perioden högst 2n.
I princip kan f vara identitetsfunktionen, det vill säga att slumptalsgeneratorn beräknar nästa tal i serien direkt utifrån det föregående. Det är också i princip möjligt att låta g ersätta S med S+1 och därmed låta f beräkna det nte slumptalet direkt. Dock är det önskvärt att ha ett tillstånd som är mycket större än de tal som matas ut, för att få en lång period och för att kunna lagra entropi så att successiva utmatningar är svåra att förutsäga.
För att en slumptalsgenerator inte ska producera samma sekvens tal varje gång den körs, bör S sättas till ett unikt värde när generatorn startas, vilket kallas för att så ett frö. Fröet beräknas ofta genom att ta den aktuella tiden från datorns systemklocka (med mikrosekundsprecision) och köra värdet genom en hashfunktion. Frön kan med fördel tas från mer avancerade hårdvarubaserade slumpkällor om sådana finns tillgängliga. Unixsystem tillhandahåller för detta ändamål en "entropipool" som till exempel påverkas av fördröjningar mellan knapptryckningar och andra störningar.
Kvalitet
Som Donald Knuth med ett ingående exempel anmärker i inledningen till kapitlet om pseudoslumptalsgeneratorer i The Art of Computer Programming, går det inte att skapa slumptal genom att sätta ihop en algoritm på måfå. Tvärtom ligger en ingående matematisk teori bakom de pseudoslumptalsgeneratorer som används idag. Bland annat bör en bra pseudoslumptalsgenerator uppfylla följande krav:
- Perioden bör vara lång. Dåliga generatorer kan ha en period på några tusen tal eller ännu färre.
- Fördelningen bör vara likformig. (Det finns användning för icke-likformiga slumptalsfördelningar, huvudsaken är att det inte förekommer stora avvikelser från den fördelning som förväntas.)
- Nära efterföljande värden bör vara oberoende av varandra.
- Alla bitar och bitmönster av respektive längd bör förekomma med samma frekvens.
- Algoritmen bör kunna implementeras effektivt. Avancerade beräkningar kan kräva miljontals slumptal som måste produceras på kort tid, utan att ge avkall på slumptalens kvalitet.
I praktiken är det svårt att mäta hur slumpmässig en serie tal är. Teoretiska och empiriska metoder finns för att upptäcka vissa specifika brister i pseudoslumptalsgeneratorer, men det går i allmänhet inte att bevisa att en generator är felfri.
Slumptal används inom kryptografi för att skapa lösenord och digitala nycklar, och för dessa tillämpningar är det av yttersta vikt att slumptalen inte uppvisar någon regelbundenhet. Förutom att den algoritm som används måste uppfylla statistiska och andra krav på slumpmässighet, krävs att frön genereras och hanteras på ett säkert sätt.
Lista över generatorer
Exempel på flitigt använda och välstuderade pseudoslumptalsgeneratorer, med olika användningsområden, är:
- linjära kongruensgeneratorer - vanligt förekommande, enkla och extremt snabba men bristfälliga
- linjärt återkopplade skiftregister
- Mersenne twister - en mer komplicerad men snabb generator med goda statistiska egenskaper och den enorma perioden 219937
- Blum Blum Shub - relativt långsam generator med bakomliggande matematisk teori som gör den kryptografiskt säker
- återkopplade hashfunktioner - kan med rätt implementation användas för att uppnå kryptografisk säkerhet
