Tilfældig talgenerator: Hvordan genererer computere tilfældige numre?

Folk har brugt tilfældige tal i årtusinder, så konceptet er ikke nyt. Fra lotteriet i det gamle Babylon til rouletteborde i Monte Carlo til terningespil i Vegas, er målet at lade slutresultatet have tilfældig chance.

Men bortset fra hasardspil har tilfældighed mange anvendelser inden for videnskab, statistik, kryptografi og mere. Dog bruger terninger, mønter eller lignende medier som en tilfældig enhed sine begrænsninger.

På grund af den mekaniske karakter af disse teknikker kræver generering af store mængder tilfældige tal meget tid og arbejde. Takket være menneskelig opfindsomhed har vi mere kraftfulde værktøjer og metoder til rådighed.

Metoder til at generere tilfældige tal

Ægte tilfældige tal

freeform elektronikrobot kigger rundt

Lad os overveje to hovedmetoder, der bruges til at generere tilfældige tal. Den første metode erbaseret på en fysisk proces og høster tilfældighedskilden fra et eller andet fysisk fænomen, der forventes at være tilfældigt .

Et sådant fænomen finder sted uden for computeren. Det måles og justeres for mulige forspændinger på grund af måleprocessen. Eksempler inkluderer radioaktivt henfald, den fotoelektriske effekt, kosmisk baggrundsstråling, atmosfærisk støj (som vi vil bruge i denne artikel) og mere.

Således siges tilfældige tal genereret baseret på sådan tilfældighed at være " sande " tilfældige tal.

Teknisk set består hardwaredelen af ​​en enhed, der konverterer energi fra en form til en anden (for eksempel stråling til et elektrisk signal), en forstærker og en analog-til-digital-konverter for at gøre output til et digitalt nummer.

Hvad er Pseudorandom Numbers?

Hacker binær angrebskode.  Fremstillet med Canon 5d Mark III og analog vintage linse, Leica APO Macro Elmarit-R 2.8 100mm (År: 1993)

Som et alternativ til "ægte" tilfældige tal involverer den anden metode til generering af tilfældige tal beregningsalgoritmer, der tilsyneladende kan producere tilfældige resultater.

Hvorfor tilsyneladende tilfældig? Fordi de opnåede slutresultater faktisk bestemmes fuldstændigt af en startværdi, også kendt som frøværdien eller nøglen . Derfor, hvis du kendte nøgleværdien, og hvordan algoritmen fungerer, kunne du gengive disse tilsyneladende tilfældige resultater.

Tilfældige nummergeneratorer af denne type kaldes ofte Pseudorandom nummergeneratorer og udsender som resultat Pseudorandomnumre.

Selvom denne type generator typisk ikke indsamler data fra kilder til naturligt forekommende tilfældighed, kan sådan indsamling af nøgler muliggøres, når det er nødvendigt.

Lad os sammenligne nogle aspekter af ægte tilfældige talgeneratorer eller TRNG'er og pseudorandomnummergeneratorer eller PRNG'er .

PRNG'er er hurtigere end TRNG'er. På grund af deres deterministiske karakter er de nyttige, når du skal afspille en række tilfældige begivenheder. Dette hjælper f.eks. Meget med kodetest.

På den anden side er TRNG'er ikke periodiske og fungerer bedre i sikkerhedsfølsomme roller som kryptering.

En periode er antallet af iterationer, som en PRNG gennemgår, før den begynder at gentage sig selv. Således vil alt andet lige være ens, en PRNG med en længere periode ville tage mere computerressourcer til at forudsige og knække.

Eksempel algoritme for Pseudo-tilfældig talgenerator

En computer udfører kode, der er baseret på et sæt regler, der skal følges. For PRNG'er generelt drejer disse regler sig om følgende:

  1. Accepter noget indledende inputnummer, det vil sige et frø eller en nøgle.
  2. Anvend frøet i en række matematiske operationer for at generere resultatet. Resultatet er tilfældigt tal.
  3. Brug det resulterende tilfældige tal som frøet til den næste iteration.
  4. Gentag processen for at efterligne tilfældighed.

Lad os nu se på et eksempel.

Den lineære Congruential Generator

Denne generator producerer en række pseudorandomnumre. Givet et indledende frø X 0 og heltalsparametre a som multiplikator, b som stigning og m som modul, defineres generatoren ved den lineære relation: X n ≡ (aX n-1 + b) mod m . Eller ved hjælp af mere programmeringsvenlig syntaks: X n = (a * X n-1 + b)% m .

Hvert af disse medlemmer skal opfylde følgende betingelser:

  • m> 0 (modulet er positivt),
  • 0 <a <m (multiplikatoren er positiv, men mindre end modulet),
  • 0b <m (denstigning er ikke negativ, men mindre end modulet), og
  • 0X 0 <m (frøet er ikke negativt, men mindre end modulet).

Lad os oprette en JavaScript-funktion, der tager de oprindelige værdier som argumenter og returnerer en matrix af tilfældige tal med en given længde:

 // x0=seed; a=multiplier; b=increment; m=modulus; n=desired array length; const linearRandomGenerator = (x0, a, b, m, n) => { const results = [] for (let i = 0; i < n; i++) { x0 = (a * x0 + b) % m results.push(x0) } return results } 

Linear Congruential Generator er en af ​​de ældste og mest kendte PRNG-algoritmer.

Hvad angår algoritmer for tilfældige talgeneratorer, der kan køres af computere, går de tilbage så tidligt som i 1940'erne og 50'erne (f.eks. Metoden Midt-kvadrat og Lehmer-generatoren) og fortsætter med at blive skrevet i dag (Xoroshiro128 +, Squares RNG og mere) .

En prøve tilfældig nummergenerator

Da jeg besluttede at skrive denne artikel om indlejring af en tilfældig talgenerator på en webside, havde jeg et valg at tage.

Jeg kunne have brugt JavaScript- Math.random()funktionen som base og generere output i pseudorandomnumre, som jeg har i tidligere artikler (se Multiplikationsdiagram - Kod din egen tidstabel).

Men selve denne artikel handler om at generere tilfældige tal. Så jeg besluttede at lære at samle "ægte" tilfældighedsbaserede data og dele min opdagelse med dig.

Så nedenfor er den "sande" tilfældige talgenerator. Indstil parametrene, og tryk på Generer.

Ægte tilfældigt talgenerator Binær decimal Hexadecimal Generer resultat:

The code fetches data from one of the APIs, courtesy of Random.org. This online resource has a plethora of useful, customizable tools and comes with excellent documentation to go with it.

The randomness comes from atmospheric noise. I was able to use asynchronous functions. That is a huge benefit going forward. The core function looks like this:

 // Generates a random number within user indicated interval const getRandom = async (min, max, base) => { const response = await  fetch("//www.random.org/integers/?num=1&min="+min+" &max="+max+"&col=1&base="+base+"&format=plain&rnd=new") return response.text() }

The parameters it takes allow a user to customize random number output. For example, min and max allow you to set lower and upper limits on generated output. And base determines if the output is printed as binary, decimal or hexadecimal.

Again, I chose this configuration but there are many more available at the source.

Når du klikker på knappen Generer, handleGenerate()kaldes funktionen. Det påkalder igen den getRandom()asynkrone funktion, styrer fejlhåndtering og outputresultater:

 // Output handling const handleGenerate = () => { handleActive(generateButton) const base = binary.checked ? 2 : decimal.checked ? 10 : 16 if (!minimum.value || !maximum.value) { prompter.style.color = 'red' prompter.textContent = "Enter Min & Max values" } else { getRandom(minimum.value, maximum.value, base).then((data) => { resultValue.textContent = data prompter.textContent = "" }).catch((error) => { resultValue.textContent = 'ERROR' prompter.textContent = 'Connection error. Unable to generate'; }) handleRestart() } } 

Resten af ​​koden beskæftiger sig med HTML-struktur, udseende og styling.

Koden er klar til at blive integreret og brugt på denne webside. Jeg adskilt det i komponentdele og leverede det med detaljerede kommentarer. Det kan let ændres. Du kan også ændre funktionalitet og stilarter efter behov.

Dette er linket til GitHub repo af den komplette kode: //github.com/sandroarobeli/random-generator