Å kunne generere tilfeldige tall er viktig i veldig mange sammenhenger, for eksempel til engangsnøkler innen kryptert kommunikasjon og til forskjellige varianter av statiskiske beregninger. Men hva mener man egentlig med «tilfeldige» tall, og hvordan kan datamaskiner, som i utgangspunktet er deterministiske vesener, generere tilfeldige tall?

Når man snakker om tilfeldige tall mener man i praksis ofte tilsynelatende tilfeldige tall. Det er gjerne tall man finner ved en deterministisk prosess, som betyr at de ikke er tilfeldige, men at de kan se tilfeldige ut for en person som ikke vet hvordan tallene blir funnet. Det finnes ulike varianter av slike prosesser, og noen er mer tilsynelatende tilfeldige enn andre. Et enkelt eksempel er desimaler i pi.

Pi er et irasjonalt tall, som betyr at tallene bak komma aldri vil ende opp som en repeterende sekvens. Disse tallene er tilsynelatende tilfeldige i den betydning at de er jevnt fordelt (alle tallene fra 0 til 9 dukker opp like ofte i gjennomsnitt) og uten noe system, men hvem som helst kan regne dem ut.

En annen lettvint måte å finne tilsynelatende tilfeldige tall er algoritmen med det festlige navnet Blum Blum Shub. Den sier enkelt og greit at du skal ta to primtall og gange dem sammen, så du får et stort tall. Dette tallet kaller vi M. Så velger du deg et annet tall, som vi kaller x₀, kvadrerer det, og tar resten av kvadratet delt på M. Eller sagt på en mer konsis måte,

For eksempel, si at vi velger

og at vi begynner med

Kvadratet av 500 er 250000, og resten av 250000/223693 er 26307 altså

26307 er dermed det første tilfeldige tallet vårt. Så gjentar vi prosessen:

Ogsåvidere. Denne måten å finne tilfeldige tall på er såkalt kryptografisk sikker, som betyr at hvis du velger tilstrekkelig store primtall til å begynne med kan ikke noen med sikkerhet si hvilken prosess du bruker for å generere tilfeldige tall uten å først observere og analysere fordømt mange tall. Graden av sikkerhet er naturligvis knyttet til størrelsen på primtallene du starter med, og det er lett å sjekke med en kalkulator eller hoderegning at hvis du begynner med for eksempel 13 og 17 er det lett å havne i et repeterende mønster. Og sant å si vil man alltid havne i et repeterende mønster, men hvis mønsteret er så langt at du aldri ser mer enn en repetisjon går det greit likevel. Her er et plot av de 1000 første tallene i rekken vi begynte på:

Men hva så med ekte tilfeldige tall? Det kan man åpenbart ikke lage med en deterministisk prosess, og dermed kan man heller ikke lage dem i et programmeringsspråk. Hvis man derimot involverer en eller annen uforutsigbar fysisisk prosess er det ganske lett å lage ekte tilfeldige tall. Som et eksempel, la oss tenke oss at du har en klokke og en Geigerteller. En Geigerteller er en dings som «goes ding when there's stuff» i betydningen at den lager lyd når den registrerer stråling fra en radioaktiv prosess. Det er alltid litt radiokativitet rundtomkring, så hvis man har en Geigerteller påslått i et vanlig rom vil man høre et klikk i ny og ne. Så tenker vi oss at hver gang du hører et klikk noterer du ned tallet sekundviseren på klokken din står på. Det er ingen måte du kan forutse når detektoren vil plukke opp noe, så dette er helt ekte tilfeldige tall, i betydningen at ingen, selv ikke du, kan vite hva det neste tallet vil bli.

Hvis du sitter på en skikkelig datamaskin har du lettvint tilgang til ekte tilfeldige tall fra /dev/random, som du kan lese ved å skrive noe slikt som

head /dev/random | uuencode -m -

Disse tallene genererer datamaskinen fra uforutsigbare fysiske prosesser som temperaturmålinger, spenningsmålinger og brukerdata som tastetrykk og musebevegelser, så dette er kvalitet.

Moralen er at hvilken type tilfeldige tall du bør bruke kommer an på hva du skal gjøre. Driver du med kryptografi er sikkert Blum Blum Shub et utmerket valg. Driver du derimot med simuleringer som baserer seg på tilfeldige tall, såkalte Monte Carlo-simuleringer, vil du sannsynligvis bruke en som går raskere å regne ut, som for eksempel Mersenne twister. Ekte tilfeldige tall er ikke alltid så enkelt å bruke hvis man trenger mange tall, fordi maskinen bruker litt tid på hente inn tilfeldige tall fra de fysiske prosessene den måler.

Sånn. Ferdig. Fornøyd nå, Ulf?

-Tor Nordam