Hash - Primzahl

[darkmasta]

sry, ich glaub ich hab mich unklar ausgedrückt:

es geht nicht um verschlüsselung, da sind primzahlen klar:

es geht um die ... ähm ... "transformierung" von einem großen wertebereich in einen kleinen, um die suche schneller zu gestalten, natürlich treten dabei kollisioen (gleiche werte) auf. um diese aber möglichst gleichmäßig zu verteilen sind primzahlen hilfreich. diese methode ist auch in fachbüchern angegeben, leider keine erklärung.

[Kiru]

Eventuell macht folgendes Probleme...

f=(int) ( (int)(Math.random()*1000*z) % z);

Dabei erzeugt Math.random eine pseudozufällige double-Zahl.

(x*y)%y=x ist natürlich immer der Fall. Klar, wenn man etwas mit y multipliziert und es danach wieder durch y dividiert, kann es keinen Rest geben, solange x ein ganzzahliger Wert ist. (und y natürlich auch)

Bsp: 3,1416*1000=3141,6
Als Rest ergeben sich die Nachkommastellen ab der 4ten,denn:
3141z+0,6z=3141,6 z

Das casten auf (int) hackt da noch ein wenig bei ab, was die Nachkommastellen etwas verfälscht, aber ich denke trotzdem, dass hier das z bei der Implementierung ganz egal ist. ((x*z) %z benutzt man eben um z.B. Nachkommastellen von x zu erhalten)

So, ich hoffe ich hab mich nun hier nicht noch bei irgendwas verhauen^^

[MagicMagor]

Ich glaube ich habe eine Ahnung was der mathematische Hintergrund davon ist, danach hattest du ja gefragt.

Grundsätzlich liefert die Modulo-Funktion ja den ganzzahligen Rest bei einer Division zweier ganzen Zahlen.
Dadurch läßt sich jede ganze Zahl durch modulo p auf ihren Rest abbilden. (p ist dein Divisor, im Prinzip eine zufällig gewählte ganze Zahl).

Wenn p jetzt eine Primzahl ist, hat deine Menge von Restklassen (bzw. die Reste, auf die du jede ganze Zahl abbildest) einige nette Eigenschaften, genau genommen bildet Z faktorisiert durch p dann einen Körper.
Die wichtigste Eigenschaft ist hierbei zum einen die Nullteilerfreiheit, wenn a*b = 0 gilt muss a oder b = 0 sein. Ist p keine Primzahl so ist dies nicht der Fall.
(Bspw bei Z modulo 6 gilt: 2*3 = 0 da 2*3 = 6 ist welches geteilt durch 6 den Rest 0 hat.)
Auch weiß man, das bei einem Körper die multiplikativ Inversen zu jeder Zahl ungleich 0 existieren und eindeutig sind. Dadurch kann man Gleichungen sehr viel einfacher lösen.

Ich denke diese Eigenschaften spielen bei der Verschlüsselung eine wichtige Rolle, weswegen man als Divisor eine Primzahl nimmt.