Gibt es einen Hash-Algo, der einen 13 Stelligen Code erzeugt?

[fastix®]

Moin!

Das kannst du doch sicher mathematisch beweisen, oder?

Das kann man sogar in einer Art begreifen, die für Kinder eingängig ist:

Mit einer nicht negativen zweistelligen Zahl des Dezimalsystems lassen sich kollisionsfrei (also eineindeutig) 100 verschiedene Items durchnummerieren. Mit einer 3-stelligen Zahl 1000, mit einer vierstelligen sogar 10.000. Also steigt die Zahl der kollisionsfreien Zuordnungen im Verhältnis zur Stellenzahl exponentiell an.

Hat man jetzt kein Dezimalsystem, sondern ein System mit einem größeren Ziffenvorrat, also 0 bis 1 und a-z (was md5 macht), dann ist das so, dass man mit einer einstelligen Zahl dieses Systems 36, mit einer zweistelligen 36 * 36 = 1.296,  mit einer dreistelligen 36^3=46.656 mit einer dreizehnstelligen 170.581.728.179.578.208.256 mit einer 32-stelligen sogar 63.340.286.662.973.277.706.162.286.946.811.886.609.896.461.828.096 Items eineindeutig zuordnen.

Da ein Hashverfahren nichts anderes ist, als eine Zahl zu berechnen, welche den übergebenen Text repräsentiert und da es unendlich viele Texte gibt, kommt man also zu dem Schluss, dass wenn man mit einem 32-stelligen Hash spätestens(!)  dem  63.340.286.662.973.277.706.162.286.946.811.886.609.896.461.828.097en Text eine bereits vergebene Nummer geben muss.

Bei 13 Stellen aber spätestens(!) schon dem 170.581.728.179.578.208.257en Text.

Die Wahrscheinlichkeit einer Kollision, also dass zwei unterschiedliche Texte der selben Zahl zugeordnet werden, wenn man nur 13 statt 32 Stellen nutzt ist demnach 36^32/36^13 = 8.983.937.243.574.936.144.818.585.412.584.022 mal höher.

Diese Zahl sieht ziemlich groß aus. Also ist es, verwendet man für den Hash nur 13 Stellen statt 32 "signifikant" wahrscheinlicher, dass zwei Texte den gleiche Hash bekommen.

Für die Zahlen danke ich den Programmierern des freien Linux-Programmes "bc".

fastix