Übungsblatt 8 
Gruppe Erik Streb Madlen Frieseke, Carsten Kötter.
 
Augabe 1)

Anmerkung: 

Wenn allerdings q = 1 ist, also r = p, dann liefert das Entschlüsselungsverfahren kein Ergebnis. (Geht man also davon aus, dass der Mitlesende p wirklich nicht kennt, wird er den Code nicht entschlüsselt bekommen. Das ist wie mit dem Safe, den der Bankräuber nicht aufgebrochen kriegt, weil der schon offen ist...) Somit wäre das die perfekte Art, die Zahl zu verschlüsseln, falls der Mithörer nicht aus dem Zusammenhang erkennen kann, das unverschlüsselt gesendet wird!

a)
Die Berechnung dauert maximal r  10-6 Sekunden, da entweder zumindest  p oder q kleiner als r ist, da sonst die resultierende Zahl pq > r wäre. Oder es ist p=q=r.  Da r die Länge 100 Bit hat, ist die größtmögliche Zahl theoretisch gleich 299 (Natürlich ist 299 nicht direkt das Produkt zweier Primzahlen, aber ich kenne das größte Produkt zweier Primzahlen unter 299 nicht, daher das theoretisch und daher werde ich auch von 299 als r ausgehen.). Damit ist der größtmögliche Wert für r = 299, also ungefähr 7,96131459  1014. Damit ergibt sich eine maximale Rechenzeit von etwa 7,9613459  108 Sekunden oder etwa 25 Jahren 89 Tagen und 12 Stunden.

Viel Spaß beim warten! Ob es sich lohnt, das so zu entschlüsseln, weiß ich nicht, die Information dürfte dann nicht mehr gebraucht werden! Gut verkürzen ließe sich die Zeit, wenn man erstmal nur durch die Primzahlen unter r teilt, und nicht durch alle Zahlen. Das setzt vorraus, das diese schon als Liste existieren, da sonst deren Berechnung die gewonnene Zeit großteils verbrauchen würde.

b) Erstmal: Da halbe Bytes ja wohl nicht belegt werden, ist die Anzahl N der Bytes von r nicht 
( log2 r )/8 sondern (log2 r )/8 aufgerundet! Naja, ist wohl nicht so wichtig. 
Daher ist r höchstens 8  2N = 2N+3 wenn N die Anzahl der Bytes von r ist. Ausgeführt werden müssen also maximal 2N+3 = 2 (N+3) / 2 = O ( 2N  ) Divisionen. (da das +3  im Exponenten durch ein c von 8 ersetzt werden könnte, was ein konstanter Wert ist.) 
Weil jede Division O(N) ist, ergibt sich dann für den Gesamtalgorithmus O( N  2N ) = O ( N  2N/2 ).