Änderungen

== Vereinfachtes Beispiel ==

Ein vereinfachtes Beispiel für eine solche Berechnung wäre eine Primfaktorzerlegung: die Zahl <math>424242</math> benötigt zur Faktorisierung mit einem in Python implementierten Algorithmus<ref>Algorithmensammlung: Zahlentheorie: Primfaktorisierung. (1. Juni 2018). Wikibooks, Die freie Bibliothek. Abgerufen am 15. November 2019, 10:51 von https://de.wikibooks.org/w/index.php?title=Algorithmensammlung:_Zahlentheorie:_Primfaktorisierung&oldid=852431.</ref> ca. 80 Schritte (und deutlich mehr CPU-Zyklen), um auf das Ergebnis <math>2 \cdot 3 \cdot 3 \cdot 7 \cdot 13 \cdot 37</math> zu kommen. Für Bob ist der Zerlegung vergleichsweise einfach zu überprüfen: er muss die Zahlen einfach nur wieder zusammenmultiplizieren und schauen, ob wieder die Ausgangszahl herauskommt.<ref group="Anm">Hier wird der Einfachheit halber vernachlässigt, dass Bob überprüfen müsste, ob die Faktoren auch wirklich prim sind, was zuungunsten der Laufzeit geht, sofern auf kein Time-Memory Tradeoff zurückgegriffen wird.</ref> Bei der Zahl 42424242 wären es für Alice bereits ~220 Schritte, bei 4242424242 über 1000.