Zufallszahlengenerator

next = (Zustand + 0x6D2B79F5) nach Multiplikation und Bitverschiebung → Wert = Minimum + ⌊next × (Maximum − Minimum + 1)⌋

Zufallsstartwert

der Ausgangszustand des Generators, eine beliebige ganze Zahl zwischen 0 und 4294967295. Er ist selbst keine Zufallsquelle, sondern nur der Punkt, an dem diese Folge beginnt – und genau deshalb liefert derselbe Startwert immer dieselbe Folge

Zustand

der laufende Zustand, der für jede erzeugte Zahl einmal neu berechnet wird. Bei dieser Aktualisierung wird der Zustand mit einer festen Konstanten und einigen Multiplikationen und Bitverschiebungen durchmischt; diese Schritte sind es, die das Ergebnis unzusammenhängend aussehen lassen, und wer sie vereinfacht, dessen erste kaputte Eigenschaft ist genau diese

Minimum, Maximum

die beiden Enden des Intervalls, beide eingeschlossen. Die Breite des Intervalls ist der Faktor, mit dem die erzeugte Kommazahl skaliert wird, weshalb jede ganze Zahl im Intervall dieselbe Chance hat

⌊ ⌋

das Abrunden. Der Generator liefert eine Kommazahl aus dem Bereich [0, 1), und das Abrunden legt sie auf genau eine ganze Zahl des Intervalls

Anzahl

wie viele Zahlen erzeugt werden sollen, höchstens 200. Bei abgeschalteten Duplikaten kann sie die Anzahl der Werte im Intervall nicht überschreiten – eine Stichprobe ohne Zurücklegen kann nicht größer sein als der Vorrat

Gebraucht wird das Werkzeug, wenn eine Folge von Zahlen verlangt ist und nicht eine einzelne Zahl: eine Stichprobe zum Nachrechnen von Hand, Testdaten, die bei jedem Lauf gleich aussehen müssen, eine Ziehung, die vor Publikum wiederholt werden soll, oder schlicht Platzhalterdaten. Dass sich der Startwert festhalten lässt, ist genau der Punkt, an dem dieses Werkzeug einer beliebigen Zufallsfunktion überlegen ist – er macht ein einmaliges Ergebnis zu etwas, das man teilen, überprüfen und zur Grundlage einer Diskussion machen kann. Soll derselbe Wert nicht zweimal vorkommen, etwa bei einer Ziehung, einer Stichprobe aus einer Liste oder einem Mischen, dann werden die Duplikate abgeschaltet. Für zwei Dinge taugt das Werkzeug allerdings nicht: Es ist keine unvorhersehbare Quelle und sollte überall dort nicht verwendet werden, wo niemand das Ergebnis erraten können darf; und es ist kein Ersatz für eine Zufallsstichprobe aus einer echten Grundgesamtheit, denn es kennt nur das Intervall und weiß über die Grundgesamtheit nichts.

1. Fünf Zahlen von 1 bis 100, und beim zweiten Lauf dieselben fünf

   1. Von 1 bis 100 gibt es 100 verschiedene Werte, jede Ziehung wählt also aus 100 Möglichkeiten
   2. Der Startwert 1 legt den Ausgangszustand fest, und die fünf Zahlen aktualisieren ihn jeweils einmal
   3. Jede erzeugte Kommazahl wird abgerundet in den Bereich 1 bis 100 gelegt: 63, 1, 53, 99, 97

   Diese fünf Zahlen sind kein Zufallstreffer und auch keine hinterlegte Tabelle: Es ist das Ergebnis des Startwerts 1, und dieselbe Eingabe in das Startwertfeld liefert sie ein zweites Mal unverändert. Beachten Sie, dass die 9,65 % das Intervall und die Anzahl beschreiben und nicht diesen einen Lauf – bei fünf Ziehungen aus 100 Werten liegt die Chance, auf ein Paar zu treffen, knapp unter einem Zehntel, ob es in dieser Folge dazu gekommen ist, ist eine andere Frage. Ein Startwert von 7 ergibt eine völlig andere Folge, während dieser Prozentwert sich keinen Deut bewegt, und das ist die sauberste Art zu sehen, welche Hälfte des Panels gewürfelt und welche gerechnet ist.

2. Sechs Zahlen von 1 bis 49, keine doppelt

   1. Der Vorrat umfasst 49 Werte, aus ihm werden sechs ohne Zurücklegen entnommen
   2. Bei jeder neuen Zahl wird geprüft, ob der Vorrat sie schon hergegeben hat, und gegebenenfalls neu gezogen – deshalb kann kein Wert zweimal erscheinen
   3. In der Reihenfolge der Ziehung gelesen ergibt das 23, 16, 33, 31, 8, 11

   Das Abschalten der Duplikate ändert an den 27,26 % nichts, und genau deshalb stehen sie neben dieser Zeile: Sie geben an, wie groß die Chance wäre, auf einen Treffer zu stoßen, wenn sechs Ziehungen einander wiederholen dürften – unabhängig davon, ob Sie es verboten haben. Daran sieht man auch, warum das Ziehen ohne Zurücklegen bei großen Zahlen immer aufwendiger wird: Aus einem Vorrat von 49 sechs Werte zu entnehmen, bedeutet schon bei mehr als einem Viertel aller uneingeschränkten Ziehungen einen Treffer, und bei 365 Werten sind es nach 23 Ziehungen bereits mehr als die Hälfte. Die Liste wird in der Reihenfolge der Ziehung ausgegeben und nicht sortiert, damit derselbe Startwert mit denselben Einstellungen immer dieselbe Folge ergibt.

3. Ein Intervall mit nur einem einzigen Wert

   1. Das Intervall enthält nur einen Wert, jede Ziehung trifft also diesen
   2. Die Trefferwahrscheinlichkeit fragt nach vier Ziehungen, und bei einem Vorrat von einem Wert muss ein Treffer entstehen
   3. Das Ergebnis lautet 7, 7, 7, 7

   Das ist die Grenze, an der der Zufallszahlengenerator aufhört, zufällig zu sein, und zu einer Konstanten wird – sehenswert, weil es der einzige Fall ist, in dem sich das Ergebnis vollständig vorhersagen lässt, bevor überhaupt gezogen wurde. Es ist zugleich die Grenze des Modus ohne Duplikate: Zwei verschiedene Zahlen aus demselben Intervall zu verlangen ist dann keine kürzere Liste, sondern ein undurchführbares Verlangen, und die Seite sagt das ausdrücklich, statt still eine Zahl weniger zurückzugeben.

Diese Zahlen gehören nicht an Stellen, an denen niemand das Ergebnis erraten können darf. Dahinter steht eine jener schnellen, kleinen arithmetischen Folgen, wie sie in gewöhnlicher Software üblich sind: Wer den Startwert kennt, kann die ganze Folge rekonstruieren, und wer einige ihrer Werte kennt, kann auf die übrigen schließen. Für Passwörter, Schlüssel, Token, Einmalkennwörter, Verlosungen mit Geld und überhaupt jede Gelegenheit, bei der Beteiligte das Ergebnis nicht vorhersagen oder zurückrechnen können dürfen, ist das Werkzeug deshalb ungeeignet – dort führt an einer kryptografischen Zufallsquelle kein Weg vorbei. Auch die Trefferwahrscheinlichkeit ist kein Urteil über die konkrete Folge vor Ihnen: Sie berechnet, unter der Annahme unabhängiger und gleichverteilter Ziehungen, die Wahrscheinlichkeit, dass in dieser Gruppe mindestens ein Paar gleicher Werte auftritt, und sie wird unabhängig davon angegeben, ob Sie Duplikate verboten haben. Ihre praktische Bedeutung liegt auf der unintuitiven Seite – schon die Quadratwurzel der Vorratsgröße genügt, damit ein Treffer sehr wahrscheinlich wird – das Geburtstagsparadoxon: Bei 365 möglichen Tagen überschreitet bereits eine Gruppe von 23 Personen die Hälfte. Ein einzelner Lauf umfasst höchstens 200 Zahlen, und übersteigt die Anzahl der Ziehungen die Zahl der Werte im Intervall, ist der Modus ohne Duplikate nicht lösbar.

Lassen sich diese Zahlen für eine Verlosung, ein Passwort oder ein Sicherheitstoken verwenden?

Nein. Es ist eine jener arithmetischen Folgen mit Startwert, wie sie in gewöhnlicher Software üblich sind, und keine kryptografische Zufallsquelle: Wer den Startwert kennt, kann die ganze Folge rekonstruieren, und wer einige ihrer Werte kennt, kann auf die übrigen schließen. Überall dort, wo Beteiligte das Ergebnis nicht vorhersagen oder zurückrechnen können dürfen – eine Verlosung mit Geld, ein Passwort, ein Schlüssel, ein Token, ein Einmalkennwort –, gehört eine kryptografische Zufallsquelle hin. Für eine Auslosung, eine Stichprobe, ein Spiel oder Testdaten dagegen, wo die Wiederholbarkeit ein Vorteil und kein Angriffspunkt ist, passt es genau.

Wozu dient der Zufallsstartwert, und warum kommen jedes Mal dieselben Zahlen?

Der Zufallsstartwert ist der Zustand, in dem diese Folge beginnt, deshalb liefert derselbe Startwert immer dieselbe Folge. Das ist beabsichtigt: Es macht das Ergebnis reproduzierbar, und genau das braucht man, wenn man eine Stichprobe weitergeben, eine Ziehung vor Publikum wiederholen oder verhindern möchte, dass Testfälle auseinanderlaufen. Ein anderer Startwert ergibt bei denselben Einstellungen eine andere Folge. Wer bei jedem Lauf etwas anderes möchte, ändert zwischen den Läufen den Startwert – der eingetragene Wert wird zusammen mit dem Ergebnis ausgegeben, die einmal lieb gewonnene Folge lässt sich also jederzeit wiederfinden.

Warum kommt es bei erlaubten Duplikaten überhaupt zu einem Treffer?

Weil die einzelnen Ziehungen voneinander unabhängig sind. Sind Duplikate erlaubt, wählt jede Position einen Wert aus dem Intervall, ohne Rücksicht darauf, was die anderen Positionen gewählt haben – und das ist das ehrliche Modell für einen Würfel oder für eine Lostrommel, in die die Kugel zurückgelegt wird. Die Trefferwahrscheinlichkeit im Panel ist die Wahrscheinlichkeit für mindestens ein gleiches Paar: bei fünf Werten aus 100 knapp 9,65 %, bei 23 Werten aus 365 schon mehr als die Hälfte – das ist das Geburtstagsparadoxon, und es ist der Grund, warum dieser Wert neben jedem Lauf steht. Soll derselbe Wert nicht zweimal vorkommen – bei einer Ziehung, einer Stichprobe aus einer Liste oder einem Mischen –, werden die Duplikate abgeschaltet.

Wird die Trefferwahrscheinlichkeit kleiner, wenn ich Duplikate verbiete?

Nein, und das Panel zeigt sie bewusst weiterhin an. Sie beantwortet nämlich genau die Frage, die man sich beim Umlegen dieses Schalters eigentlich stellt: Wie groß wäre die Chance auf einen Treffer gewesen, wenn Duplikate nicht verboten wären. Sechs Zahlen aus 1 bis 49 ergeben 27,26 %, das Verbot wehrt also ein reales Risiko ab und nicht bloß eine theoretische Möglichkeit. Daraus erklärt sich auch, warum das Ziehen ohne Zurücklegen bei großen Zahlen langsam und schließlich unlösbar wird – sobald die Anzahl der Ziehungen die Zahl der Werte im Intervall übersteigt, gibt es überhaupt keine gültige Antwort mehr, und die Seite sagt das ausdrücklich, statt eine kürzere Liste zurückzugeben.

Wie viele Zahlen passen in einen Lauf, und welche Grenzen hat das Intervall?

Ein Lauf umfasst höchstens 200 Zahlen; die Endpunkte des Intervalls müssen ganze Zahlen sein, und das Minimum darf nicht größer als das Maximum sein. Die Werte selbst dürfen negativ sein, ein Intervall von −50 bis 50 ist also zulässig. Nicht ganzzahlige Endpunkte führen zu einem Fehler und nicht zu einer Rundung: Im Modus ohne Duplikate würde das Ziehen aus einem Intervall mit Kommazahlen die Regel „ohne Wiederholung“ ihrer Bedeutung berauben, und eine Liste, die plausibel aussieht, aber die eigenen Einstellungen verletzt, ist weit schlimmer als eine Fehlermeldung.

Werden die erzeugten Zahlen sortiert?

Nein – sie werden in der Reihenfolge der Ziehung ausgegeben, und diese Reihenfolge gehört zum Ergebnis. Ein Sortieren würde die Information zerstören, die für die Wiederholbarkeit aus dem Startwert gebraucht wird, und dort, wo die Position selbst Bedeutung trägt – beim Mischen einer Reihenfolge oder beim Austeilen von Karten –, würde es den Sinn unmittelbar verändern. Wer eine geordnete Ziehung braucht, kopiert das Ergebnis heraus und sortiert es selbst; die Ziehung behält die Reihenfolge, die der Startwert vorgibt.

• Zufallszahlenerzeugung in Browsern — Analyse der Zufallszahlenerzeugung in Browsern: warum ein Startwert die ganze Folge festlegt und warum eine solche Folge nicht als Sicherheitsmerkmal taugt — Bundesamt für Sicherheit in der Informationstechnik (BSI)
• SP 800-90A Rev. 1, Recommendation for Random Number Generation Using Deterministic Random Bit Generators — NIST CSRC (English original; the official recommendation on deterministic random bit generators and thus the authority behind «the seed determines the whole output») — National Institute of Standards and Technology (NIST), Computer Security Resource Center
• Birthday Problem — from Wolfram MathWorld (English original; the closed form of the collision probability as one minus a falling factorial over the size of the pool, which is the basis of this page's repeatChance) — Wolfram MathWorld
• 1.3.6.1. What is a Probability Distribution — e-Handbook of Statistical Methods (English original; the frequency reading of probability, that is, what a statement like «knapp unter einem Zehntel» actually claims) — National Institute of Standards and Technology (NIST)