Auf Multiplikation basierende Hash-Funktionen III

Satz von Hugo Steinhaus und Vera Turán Sós:

Sei theta eine irrationale Zahl. Wenn die Punkte { theta }, {2 theta }, ..., {n theta } in das Intervall [0,1] plaziert werden (jeweils mod 1), dann haben die dadurch entstandenen n+1 Teilintervalle von [0,1] maximal drei verschiedene Längen. Wenn der nächste Punkt {(n+1) theta } hinzugefügt wird, dann fällt er in eines der längsten Segmente.

Dieser Satz stellt sicher, daß diese Punkte sehr gleichmäßig über das Intervall von [0,1] verteilt werden und damit darauf basierende Hash-Funktionen eine gute Streuwirkung besitzen.

Allerdings gibt es durchaus Unterschiede in der Wahl von theta , die sich in den möglichen Größenunterschieden der Intervalle bemerkbar machen. Wenn beispielsweise theta nahe bei 0 oder 1 gewählt wird, würde es zu Beginn viele winzige Teilintervalle und ein großes geben.

Der goldene Schnitt ^-1 = (sqrt(5) - 1) / 2 ist ein idealer Kandidat für theta , wenn eine möglichst gleichmäßige Verteilung gewünscht wird.

A sollte dann als die nächstgelegene ganze Zahl zu ^-1w gewählt werden, die teilerfremd zu w ist.

Somit ist beispielsweise A = 1327217883 geeignet für w = 2³¹.

	Dieser Satz stellt sicher, daß diese Punkte sehr gleichmäßig über das Intervall von [0,1] verteilt werden und damit darauf basierende Hash-Funktionen eine gute Streuwirkung besitzen.
	Allerdings gibt es durchaus Unterschiede in der Wahl von , die sich in den möglichen Größenunterschieden der Intervalle bemerkbar machen. Wenn beispielsweise nahe bei 0 oder 1 gewählt wird, würde es zu Beginn viele winzige Teilintervalle und ein großes geben.
	Der goldene Schnitt ^-1 = (sqrt(5) - 1) / 2 ist ein idealer Kandidat für , wenn eine möglichst gleichmäßige Verteilung gewünscht wird.
	A sollte dann als die nächstgelegene ganze Zahl zu ^-1w gewählt werden, die teilerfremd zu w ist.
	Somit ist beispielsweise A = 1327217883 geeignet für w = 2³¹.