Den perfekta slumpgeneratorn

[Digitum]

Som många av er vet så finns det ingen perfekt slumptalsgenerator eftersom man per definition inte kan mäta kvaliteten på ett slumptal med större noggrannhet än att man kan göra det sannolikt att en serie tal är slumpmässigt utvalda. Känner man till tillräckligt många variabler så bör man kunna räkna ut vad som händer, även om denna princip står i strid om principen om den fria viljan.

Det finns stora, dyra, professionella slumptalsgeneratorer som levererar tal som enligt vissa håller hög kvalitet, sådana som tex Svenska Spel och en del kasinon använder.

Jag har funderat på hur man på ett billigt och relativt enkelt sätt kan bygga en hårdvarubaserad slumptalsgenerator. Vilken princip skall man använda och vilken metod är bäst för utvärdering av resultaten? hur detekterar man avvikelser? Hur ofta behöver man få ut ett slumptal av hög kvalitet från enheten?

Brusgenerator? Finns risk för att de genererar regelbundna mönster som kan påverka mätningen. Enheter som g-kraftmätare, ljudsensorer och lufttrycksmätare skulle kunna öka på kvaliteten då det är svårt att kompensera för fel i enheterna under förutsättning att man inte får direkt tillgång till själva källan för att tex kunna mäta statistiska avvikelser. Vad har ni för idéer?

[Icecap]

Kvaliteten av slumptal beror ju på ett antal faktorer.
* Antal bit.
* Viktningen av de olika värden.

Men skär man ner till benet är det helt och totalt viktigaste att man ha en slumpmässig bitström med en exakt duty-cycle på 50% som inte påverkas av något alls. Ut ifrån den kan man sedan extrahera det antal bit man behöver för de data man behöver.

Så jag lutar mot termisk brus. Man kan sedan extrahera större värden än 1 bit vid att sampla med fasta intervall - eller evt. med intervall som bestäms av en annan brus-generator.

[calmar]

Radioaktivt sönderfall är en bra seedgenerator till en slumpgenerator och relativt lätt att mäta - stoppa in en fotodiod och en strålkälla i en skärmad burk.

[sodjan]

> Hur ofta behöver man få ut ett slumptal av hög kvalitet från enheten?

Det är väl snarast än fråga till dig? Varför frågar du *oss*?
Vad ska du ha "enheten" till?

Svar på generella frågor kring slumptal finns bl.a här:
https://en.wikipedia.org/wiki/Random_number_generation

En site på nätet som har en del slumptals tjänster:
https://www.random.org
"RANDOM.ORG is a true random number service that generates randomness via atmospheric noise."

De har en web baserad tjänst där t.ex URL'en:
https://www.random.org/integers/?num=10 ... in&rnd=new
ger som svar (t.ex):

Kod: Markera allt

28	85	73	95	69	24	46	74	51	96
29	73	63	37	70	98	72	95	22	39
98	21	33	29	54	39	79	86	48	49
71	72	66	19	51	55	28	87	98	65
85	27	51	91	30	36	55	25	19	51
63	85	45	64	70	35	14	63	42	87
98	36	57	 9	53	 7	85	61	77	23
64	42	68	 3	18	33	 9	12	17	32
59	 5	81	87	19	53	10	95	63	47
37	13	10	92	16	93	48	10	70	94

Eller testa: https://www.random.org/coins/?num=5&cur=60-sek.1kr

[4kTRB]

En lägerbrasa som sprakar, ger den regelbundna mönster tro?

[Nerre]

Nån form av naturligt brus är väl det klassiska. Om jag inte missförstått så körde CIA i alla fall förut med vitt brus inspelat på CD-skivor som krypteringsnycklar. (Bägge sidor behövde alltså ha samma CD för att kunna dekryptera datat.)

[danei]

Det är ju en idiotsäker kryptering. Så den används nog fortfarande även om USB minnen kanske är smidigare i dag. Det gäller bara att de till att ingen får tag i nyckeln.

[4kTRB]

Nu vet jag inte om det går använda som
slumpgenerator men kaos verkar ju inte
så hemskt förutsägbart.
Chua's circuit är ju ett exempel på en
enkel krets som är noga analyserad.

https://en.wikipedia.org/wiki/Chua%27s_circuit

Boken Chua skrivit är för övrigt en grymt läsvärd bok i
elkretsteori. Linear and Non-linear Circuits
amazon.co.uk: Linear and Non-linear Circuits [Paperback]

[blueint]

Det finns en hel del information i wikipediaartikeln random number generation:
"radioactive decay, thermal noise, shot noise, avalanche noise in Zener diodes, clock drift, the timing of actual movements of a hard disk read/write head, and radio noise"

Samt hardware random number generator.

Alltså dessa exempel på källor finns:
* Radioaktivt sönderfall, exempel: brandvarnare med backspänd diod
* Brus från resistanser och PN-övergångar (transistorer med vitt brus)
* Strömvariationer i radiorör ger Skottbrus
* Zenerdioder som arbetar nära genombrottsspänningen ger lavinbrus
* Skillnaden mellan två klockors omslagstider ger klockdrift
* Radiobrus som dock kanske är opålitligt om någon sändare dyker upp
* Brownsk rörelse genom att observera små partiklar i mikroskop osv.
* Strömvariationer genom CCD/CMOS bildsensorer utan ljusexponering genom mörkerström. Dock måste man först filtrera för olika biasdefekter som alla sensorer har.
* Optiska fenomen såsom LSB från bildströmmar som t.ex rök, bubblor
* Splittring av lasergenererade fotoner genom en kristall
(fler källor?)

Ett projekt som genomfördes 1946 och publicerades 1955 i form av en slumptalsbok använde ett miniatyr radiorör i form av tyratronen 6D4 med en ström på 5 mA genom sig samt en belastning ("load resistance") på 20 kOhm ett samtidigt precist magnetfält på 37,5 mT orsakar då att de normalt sett stabila elektronflödena blir kaotiska. Om detta kan man läsa i rapporten Rocks and Code (2009). Troligtvis får man resultatet i form av varierande ström.
Står så här också om detta fenomen i "6D4 electron tube reference, Sylvania.": "Gas diode and thyratron electron tubes in a crosswise magnetic field can generate substantial noise energy (10 volts or more into high impedance loads) but have a very peaked energy distribution and require careful filtering to achieve flatness across a broad spectrum."

Att jag nämner just detta projekt är för att det högst troligt är genomfört med stor omsorg av ett bra resultat och verkar relativt enkelt att genomföra.

Så det är bara att välja de metoder som du klarar att genomföra och har råd med.

[Glenn]

Silicon graphics (på den tiden dom verkligen ledde utveckling) genererade ju slump via lavalampor ett tag, det var nog iofs delvis en gimmick men det var tydligen väldigt slumpvisa former.

[blueint]

Fast wikipedia skriver:

One problem was determining whether the chaotic shapes generated were actually random — the team decided that they are in properly operating Lava lamps.

Så det är väl en bra idé men kvaliten på slumpdatat kanske kan ifrågasättas?

[/mr]

En "slumptalskälla" som inte nämnts är tiden. Om en apparat har en klocka, och användaren inte kan veta vad den klockan kan vara, så kan tiden - eller åtminstone de minst signifikanta siffrorna i den - vara tillräckligt godtyckliga för att agera slumptal eller frö till slumptalsgenerering.

[Icecap]

/mr: helt säkert! Om man ska simulera t.ex. tärningskast kan man ha en räknare som kör 1-6 - snabbt! Kanske med en 100Hz timer-interrupt.

Ska man sedan trycka på en knapp för "nästa tärningskast" är det - som människa - ganska omöjligt att trycka knappen in på "rätt" 1/100 del sekund så tiden är verkligen en bra hjälp där.

Problemet kommer dock vid slumptal som behöver ett stort område av värden, då blir den metod inte speciellt korrekt.

[/mr]

I det sista fallet borde det ändå vara användbart som del av lösningen. Tillsammans med en annan begränsad slumptalsgenereringsmetod kan de utvidgas till ett mycket större område av värden.

Om man t ex har möjlighet att avläsa tiden vid tre oberoende slumpmässiga tillfällen, och få slumptal med tre värdesiffror vid vardera tillfället, så borde de kunna kombineras ihop till ett slumptal med nio värdesiffror.

[blueint]

Entropi från oscillatorer används kommersiellt har jag fått veta
I synnerhet när en oscillator används för tidpunkten för att mäta antal cyckler som en annan oscillator har avverkat sedan förra gången. Är oscillatorerna perfekta blir det samma antal steg varje gång. Men så är det alltså ej. Utan kvanteffekter är tydligen med och påverkar processen. Sedan behövs en viss efterbearbetning.