Slumptall

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

En ekte slumptallsgenerator  for å lage ekte slumptall er terningkast, myntkast eller kuler med tall i en Lotto-maskin, men i datamaskiner er det uekte slumptallsgeneratorer  (PRNG- «pseudorandom number generator») som lager pseudoslumptall (pseudorandome tall, uekte slumptall) 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 av flere matematiske funksjoner og regneprosesser. Med en spesiell kommando eller frø ("seed") 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. Frøet er ofte et stort tall som det er umulig å gjette seg til. 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 (modulær matematikk) blir ofte brukt som utgangspunkt for kryptografering f.eks. RSA-kryptering (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" til alle krypteringssystemer.

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 enkel måte å lage pseudoslumptall er via en lineær kongruent generator, men denne er ikke sikker nok til å lage gode pseudoslumptall, men ble bl.a. brukt i JAVA.

\(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

Middelkvadrat metoden ble utviklet av John von Neumann i 1949 og baserer seg på to store tall multiplisert med hverandre. Deretter tar med tar de siste 6 sifferne i dette produktet og multipliserer med hverandre, og slik fortsetter man. Et starttal kan for eksempel være antall sekunder etter UNIX-fødselsdag (Klokken 00:00:00 UTC 1. januar 1970). 

«Seed»-basert autentifisering kan bli brukt i brikker med bank-id, som har fått forhåndsprogrammert et unikt tall som «seed» og som genererer pseudoslumptall basert på en algoritme, men hvor banken har mulighet til å koble starttallet  unikt for brikken (frøet eller «seed») og det 11-siffrete personnummeret for bruker-id. Dette prinsippet  kan også anvendes innen autentisering med engangsbruk passord i apper på en smartmobiltelefon. En slumptallsgenerert engangskode (engangspassord) gir større sikkerhet enn brukernavn og et passord. Det blir også utviklet biometriske autentiserings- og verifiseringsalgoritmer.

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 3. mai 2021 13:06