Nun haben wir uns einige Zeit mit Primzahlen beschäftigt, jetzt soll es um das "Gegenteil" von Primzahlen, die zusammengesetzten Zahlen gehen. Wenn man im Mathematikunterricht der Mittelstufe einen Bruch auf denselben Nenner bringen will (oder soll), so benötigt man die Primfaktorzerlegung der einzelnen Nenner.
Bei kleinen Zahlen hilft man sich durch rumprobieren und findet dann leicht die Primfaktoren. Was kann man bei großen Zahlen tun?
Wenn man versucht, die zu untersuchende Zahl n nur durch alle die Primzahlen, die kleiner als Wurzel von n sind, zu teilen, so erleidet man schnell Schiffbruch: Bereits bei einer 20-stelligen Zahl sind ca 300 Millionen Divisonen nötig, bei einer 40-stelligen schon 2,2 Trilliarden. Das übersteigt die Rechenleistung der heute leistungsfähigen Rechner. Die heute eingesetzten Verfahren, um so große Zahlen zu faktorisieren, sind sehr kompliziert. (Schulz, 1993; Schulz 1996)
Ein Schlüssel zur Kryptographie liegt darin, wieviel Zeit man benötigt, um sehr große Zahlen (ca. 150 Stellen) in ihre Primfaktoren zu zerlegen. In Aufgabe 4 soll untersucht werden, wieviel Zeit für verschiedene Zahlen bei der Primfaktorzerlegung benötigt wird und wie die Faktorgröße von der Zeit abhängt.
Aufgabe 4: Untersuche die Faktorisierungszeit von großen Zahlen (MuPAD-File: factn.mus, TI-92+/Voyage200: faktzeit.v2p).
zurück 