1999 sagte der Forscher Ron Rivest dem Puzzle eine Berechnungsdauer von 35 Jahren voraus, nun ist es geknackt.

Die Zukunft vorherzusagen ist selten ein leichtes Unterfangen, in Bezug auf den technologischen Fortschritt gilt das um so mehr. Trotzdem haben Ron Rivest und David Wagner 1995 genau das versucht: Sie stellten ein Rätsel in Form einer Matheaufgabe und trafen einige Annahmen wie sich die Rechengeschwindigkeiten von Computern wohl entwickeln würden. Die vollständige Aufgabe kann man online nachlesen, sie ist aber recht schnell beschrieben:

The problem is to compute 2^(2^t) (mod n) for specified values of t
and n.  Here n is the product of two large primes, and t is chosen to
set the desired level of difficulty of the puzzle.

Es geht also darum die Zahl 2 mit 2 "hoch" t zu potenzieren. Für t = 3 ergäbe sich damit 2 "hoch" 3 = 2 * 2 * 2 = 8. Und diese 8 ist dann wiederrum die Potenz für die äußere 2, da berechnet man dann also 2 "hoch" 8 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256. Mit dieser Rechnung hat man aber nur einen Teil des Rätsels gelöst. Die berechnete Zahl 256 muss noch durch n geteilt werden. Allerdings ist bei dieser speziellen Rechenoperation "mod" (oder "Modulo") nicht das "normale" Ergebnis der Division interessant, sondern der ganzzahlige Rest. Das funktioniert ziemlich genau so, wie man Teilen mal in der Grundschule kennengelernt hat. 13 "durch" 5 war damals halt = 2 Rest 3. Und eben diesen Rest ist das Ergebnis der Modulo Operation. Wenn man für unser Beispiel nun also n = 5 wählen würde, wäre das Ergebnis für diese Zahlen 256 "mod" 5 = 1. Für größere Zahlen muss man diese Division allerdings nach jedem Schritt ausführen. Man kann dann nicht mehr wie im Beispiel einfach die Potenz sofort ausrechnen und dann nur einmalig dividieren. Rivest und Wagner liefern selbst das folgende Beispiel:

Suppose n = 11*23 = 253, and t = 10.  Then we can compute:
	2^(2^1) = 2^2 = 4 (mod 253)
	2^(2^2) = 4^2 = 16 (mod 253)
	2^(2^3) = 16^2 = 3 (mod 253)
	2^(2^4) = 3^2 = 9 (mod 253)
	2^(2^5) = 9^2 = 81 (mod 253)
	2^(2^6) = 81^2 = 236 (mod 253)
	2^(2^7) = 236^2 = 36 (mod 253)
	2^(2^8) = 36^2 = 31 (mod 253)
	2^(2^9) = 31^2 = 202 (mod 253)
	w = 2^(2^t) = 2^(2^10) = 202^2 = 71 (mod 253)

Allerdings haben Rivest und Wagner nochmal wesentlich größere Zahlen für n und t gewählt. Konkret haben Sie für n zwei sehr große Primzahlen multipliziert, dadurch wird die Division vergleichsweise schwierig. (Warum die Division dadurch schwierig wird, wäre nochmal Stoff für einen eigenen Beitrag.) Und weil man mit der Zahl t steuern kann, wie oft die Zahlen eigentlich multipliziert werden sollen, haben Rivest und Wagner darüber die vermutliche Dauer der Berechnung festlegen wollen. Konkret haben Sie sich für die folgenden Werte entschieden:

n = 631446608307288889379935712613129233236329881833084137558899
    077270195712892488554730844605575320651361834662884894808866
    350036848039658817136198766052189726781016228055747539383830
    826175971321892666861177695452639157012069093997368008972127
    446466642331918780683055206795125307008202024124623398241073
    775370512734449416950118097524189066796385875485631980550727
    370990439711973361466670154390536015254337398252457931357531
    765364633198906465140213398526580034199190398219284471021246
    488745938885358207031808428902320971090703239693491996277899
    532332018406452247646396635593736700936921275809208629319872
    7008292431243681

t = 79685186856218

Und für diese Werte wurde das Rätsel vor kurzem, also nach nur 20 Jahren, gelöst. Wie das genau ging, werden wir in zwei Wochen besprechen. Das Titelbild zeigt den Belgier Bernard Fabrot, der das Rätsel gelöst hat.