Das Diskrete Logarithmusproblem

Wir brauchen ein numerisches Verfahren, das in eine Richtung einfach und in die andere schwierig ist. Das bringt uns zur modularen Arithmetik, auch bekannt als Uhrenarithmetik. Zum Beispiel, um 46 mod 12 zu finden, könnten wir ein Seil nehmen, welches 46 Einheiten lang ist und es um eine Uhr mit 12 Einheiten wickeln. Dies wird als Modulo bezeichnet, und wo das Seil endet, ist die Lösung. Wir sagen also 46 mod 12 ist kongruent zu 10, ganz einfach. Damit das klappt, benutzen wir einen Primzahlen modulo, wie z.B. 17, dann finden wir eine Primitivwurzel von 17. In diesem Fall drei mit der wichtigen Eigenschaft, dass wenn sie mit verschiedenen Exponenten multipliziert wird, sich die Lösung gleichmäßig um die Uhr verteilt. Die Drei wird als Generator bezeichnet. Wenn wir drei auf einen beliebigen Exponenten x potentieren, dann ist die Lösung genauso wahrscheinlich wie jede ganze Zahl zwischen 0 und 17. Das umgekehrte Verfahren ist schwierig. Angenommen, wir bekommen 12 und sollen herausfinden, auf welchen Exponenten drei potentiert werden muss. Dies wird als diskretes Logarithmusproblem bezeichnet. Und jetzt haben wir unsere Einwegfunktion, die einfach auszuführen, aber schwierig umzukehren ist. Bei 12 müssten wir uns auf Versuch und Irrtum verlassen, um passende Exponenten zu finden. Wie schwierig ist das? Mit kleinen Zahlen ist es einfach, aber wenn wir einen Primzahlen-Modulus verwenden, der hunderte von Stellen lang ist, wird es praktisch unmöglich, es zu lösen. Selbst wenn du Zugang zu aller Rechenleistung auf der Erde hättest, könnte es Tausende von Jahren dauern, um alle Möglichkeiten durchzugehen. Die Stärke einer Einwegfunktion basiert also auf der Zeit, die benötigt wird, um sie umzukehren.