Pseudo-Zufallszahlen-Generator?

Hallöchen, habe mir zum Einstieg ins Programmieren mit C++ eine Art 'Zufallszahlen-Generator' gebastelt, und wüsste gerne,
inwiefern ich jetzt überprüfen soll, ob die generierten Zufalls-
zahlen ausreichend unvorhersagbar sind, um sie als 'zufällig' zu bezeichnen.

Hier mein aller-erster C++ Gehversuch:

class MyPRNG{
private:
	unsigned __int64 seed;
	union{
		double f;
		unsigned __int64 u;
	}X;
public:
	MyPRNG(unsigned __int64 xseed){
		this->seed = xseed & 0x3FFFFFFFFFFFFFFF;
		this->X.f = 1.73205080757;
	}
	unsigned __int64 rnd(){
		seed ^= X.u;
		X.u >>= (seed & 1u);
		X.f *= 1.73205080757;
		return X.u;
	}
};

#include <ctime>
#include <cstdlib>
#include <cstdio>
using namespace std;

int main(void){
	FILE* out = fopen("MyRand.txt", "w");
	MyPRNG test = (unsigned __int64) time(NULL) * (time(NULL)-1ull);
	for(unsigned i = 0u; i < 0xFFFF; ++i) /* Erzeugt 65535 'Zufallszahlen' von 0 bis 1048575*/
		fprintf(out, "%I64u\n", test.rnd() & 0xFFFFF);
	fclose(out);
	system("PAUSE");
	return 0;
}

(Anm.Zum 'schnellen' Testen kürzerer Programme erscheinen mir printf() & Friends
sehr praktisch & unkompliziert zu sein.)

Das Programm gibt ca. 65000 zufällige Zahlen aus dem Bereich von
0 bis ca. 1 Mio in eine Datei "MyRand.txt" aus.
Bei einer Inspektion der erzeugten 'Zufalls-Zahlen-Datei' erscheinen mir
die Zahlen jedenfalls zuhöchst unvorhersagbar und 'zufällig',
nur wie müsste man so viele Zahlen eigentlich systematisch analysieren,
damit man sie als (pseudo-)zufällig bezeichnen 'darf'?

Ist die Idee mit dem union für double bzw. __int64 (VisualC++! der Typ könnte in
anderen Umgebungen anders heißen!) eigentlich generell eher gut oder eher
schlecht dazu geeignet, Pseudo-Zufallszahlen zu basteln?

Anstatt der Multiplikation mit Quadrat-Wurzel 3 könnte man gewiss auch ebensogut
eine x-beliebige andere (irrationale) Wurzel verwenden, sodass man sich
theoretisch eigentlich beliebig viele verschiedene Pseudo-Zufallszahlen-
Generatoren nach dem selben Schema basteln kann, von denen die allermeisten
wohl gänzlich unterschiedliche und - aus meiner laienhaften Sicht -
jedenfalls völlig unvorhersagbare Zufallszahlen ausspucken dürften.

Ab wann (und ob überhaupt) sich die generierte Zufalls-Folge jemals
wiederholt, konnte ich auch bei einem Probe-Lauf der Schleife bis 1 Mio.
noch nicht herausfinden. Womöglich könnte man die Bitmuster auch zu
XOR-Verschlüsselungs-Zwecken irgendwelcher geheimer Nachrichten verwenden.
Wäre das ein 'sicheres' Verfahren, oder eher nicht zu empfehlen?

Danke schonmal für Erläuterungen, ob mein Algorithmus mit dem union zu
etwas taugt bzw. welche Probleme es damit geben könnte.

cooky451

Erstmal ist das so nicht standardkonform. Nicht nur wegen __int64 (das man einfach gegen std::uint64_t austauschen könnte ), sondern auch wegen dem union Zugriff. Du darfst nur das Element lesen, in das als letztes geschrieben wurde.

Wie man analysiert ob die Zahlen "gut" sind? Na ja, ich würde mal sagen man macht verschiedene statistische Analysen. Sind die Zahlen gleich verteilt? Ist die nächste Zahl wahrscheinlich höher als die davor? (Oder umgekehrt.) etc. Alles was einem so einfällt. Ob und wie man den Algorithmus selbst mathematisch analysieren kann, weiß ich nicht.

Zur xor Verschlüsselung: Prinzipiell wäre das möglich. Aber dafür müsste der 1. wirklich, wirklich gut sein und 2. sind 64 bit Keys nicht mehr ganz ausreichend bei dem aktuellen Stand der Technik.

SeppJ

Hier findest du ein Testprogramm zum Testen von Zufallszahlengeneratoren:
http://www.phy.duke.edu/~rgb/General/dieharder.php
(edit: Hier noch einer, keine Ahnung, ob der was taugt. Fand ich aber interessant, weil online:
http://www.cacert.at/random/
)

Dies testet die "Zufälligkeit" der Zahlen, keine sonstigen Qualitäten, zum Beispiel ob der Generator für kryptografische Anwendungen geeignet wäre (deiner ist es übrigens nicht).

Womöglich könnte man die Bitmuster auch zu
XOR-Verschlüsselungs-Zwecken irgendwelcher geheimer Nachrichten verwenden.
Wäre das ein 'sicheres' Verfahren, oder eher nicht zu empfehlen?

Nein, XOR-Verschlüsselung ist entweder
a) lächerlich einfach zu knacken
oder
b) die Schlüssellänge ist unpraktisch groß, d.h. wenn man den Schlüssel sicher übermitteln konnte, dann hätte man auch gleich die Nachricht übertragen können.

Bei b) kommt noch hinzu: Keine Pseudozufallszahlen! Das ist nur mit echten Zufallszahlen sicher. Also: Vergiss XOR für ernsthafte Anwendungen, das ist nur Spielzeug.

cooky451

@SeppJ
Was XOR angeht solltest du dich noch mal informieren. Siehe z.B. https://en.wikipedia.org/wiki/Block_cipher_modes_of_operation insbesondere bei CTR.

SeppJ

cooky451 schrieb:

@SeppJ
Was XOR angeht solltest du dich noch mal informieren. Siehe z.B. https://en.wikipedia.org/wiki/Block_cipher_modes_of_operation insbesondere bei CTR.

Ich bin mir sicher, der TE meinte eine naive XOR-Verschlüsselung, kein Blockchiffre. Blockchiffres sind gut . Falls ich dem TE unrecht getan haben sollte: Entschuldigung, aber dein Eingangsbeitrag klang so naiv.

Michael E.

Totalanfänger schrieb:

Anstatt der Multiplikation mit Quadrat-Wurzel 3 könnte man gewiss auch ebensogut
eine x-beliebige andere (irrationale) Wurzel verwenden, sodass man sich
theoretisch eigentlich beliebig viele verschiedene Pseudo-Zufallszahlen-
Generatoren nach dem selben Schema basteln kann, von denen die allermeisten
wohl gänzlich unterschiedliche und - aus meiner laienhaften Sicht -
jedenfalls völlig unvorhersagbare Zufallszahlen ausspucken dürften.

Du multiplizierst nicht mit sqrt(3), sondern einer Näherung davon. Irrationale Zahlen kannst du nicht exakt speichern. Daher ist deine Wahl so gut wie jede andere auch, die ebenso viele Nachkommastellen hat. Und völlig unvorhersehbar sind deine Zufallszahlen auch nicht. Oder hast du eine Gleichverteilung unter den gezogenen Zahlen? Als Anfänger versucht man die Zahlen oft noch etwas "zufälliger" zu machen, indem man eine weitere obskure Operation einfügt. In den allermeisten Fällen werden die Zufallszahlen durch jeden weiteren Schritt schlechter.

Danke für die Tipps und die Links.
Werde mir also einfach mal ein paar Statistik-Funktionen basteln,
um die Zahlen in der Datei zu analysieren.
mfg