Slumptall

Slumptall er tilfeldige tall brukt innen statistikk, simuleringer, modellering (Monte Carlo, Markovkjeder),  kryptografi og  autentisering (privat nøkkel-offentlig nøkkel,  bankkode, kredittkortnummer). Slumptall kan være ekte slumptall eller pseudoslumptall laget i en deterministisk algoritme. Pseudoslumptall ser tilsynelatende tilfeldige ut, men er det ikke.

En ekte slumptallsgenerator  for å lage slumptall er terningkast eller myntkast, men i datamaskiner er det uekte slumptallsgeneratorer  (PRNG- «pseudorandom number generator») som lager pseudoslumptall (pseudorandome tall) basert på en algoritme. Pseudorandome tall vil i praktisk bruk oppføre seg omtrent som tilfeldige tall, hvis det ikke settes altfor store krav til kryptografisk sikkerhet. Slumptall benyttes i Monte Carlo simuleringer og innen kryptografi. At tallene virkelig er tilfeldige, og ikke følger et mønster er derfor av avgjørende betydning, noe som John von Neumann påpekte. I statistikkpakker på en datamaskin velge pseudoslumptall fra forskjellige statistiske fordelinger for eksempel normalfordelingen, uniform fordeling, kjikvadratfordelingen osv. Generering av slumptallene blir styrt av en funksjon, og med en spesiell kommando eller frø kan man få en slumptallsgenerator til å starte fra samme sted, noe som gjør at man får samme resultat hver gang man genererer slumptall. Dette er svært viktig hvis man skal lage reproduserbare simuleringer. Som utgangsmetode for produksjon av slumptall i statistikkpakken R benyttes Mersenne twister, utviklet av Makota Matsumoto og Tauji Nishimura i 1998, hvor perioden for gjentakelse er 219937-1 iterasjoner, tilnærmet lik 4.32·106001, 32-bits tall jevnt fordelt i 623 dimensjoner basert seg på en lineær kongruent generator kombinert med primtallene. jfr. Mersenne-primtall 2n-1. Faktorisering av store primtall og modulusregning blir ofte brukt som utgangspunkt for kryptografering f.eks. RSA (Ron Rivert, Adi Shamir &Leonard Adleman ved MIT). Man er stadig på jakt etter nye sikre metoder innen kryptografi e.g. kvantekryptografi, elliptiske kurver kryptografi. For NIST SP 800-90A  (National Institute of Standards and Technology, Special publication, Recommendation for Random Number Generation Using Deterministic Random Bit Generators) ble NSA beskyldt for å ha en "kleptobakdør".

Målet for en simulering er å gjenta en enkel prosedyre millioner av ganger, som erstatning for mer komplekse beregninger, og som det i mange tilfeller også er umulig å utføre.

Lineær kongruent generator

En måte å lage pseudoslumptall er via en lineær kongruent generator:

\(x_{i+1}=ax_i + b\pmod d\\ \;\;a>0, \;\; b\geq 0, \;\;\;i=1, 2, 3, ..., n\)

hvor a er multiplikator, b er økningen, og d modulus (mod). Verdien av d bør være mye større enn n.

Et lite eksempel plukker ut n = 10000 tilfeldige tall mellom 0-100 med denne generatoren, og for de tilfeldige parameterverdiene  a=789, b=16784, d=65347, s=17 (startverdi i generatoren). Det er ikke lett å bedømme om disse tallene forekommer tilfeldig eller ikke, om det er et mønster eller ikke, selv i dette lille eksemplet

Slumptall

Litteratur

 R Core Team (2016). R: A language and environment for statistical  computing. R Foundation for Statistical Computing, Vienna, Austria.
  URL https://www.R-project.org/.

Wikipedia

Tilbake til hovedside

 

Publisert 12. des. 2018 13:04 - Sist endret 27. nov. 2019 10:21