Zum Hauptinhalt springen

Zwei Beispiele: Faktorisierung und ggT

Die klassischen Computer von heute sind unglaublich schnell, und ihre Leistung scheint ständig zuzunehmen. Manche könnten deshalb verleitet sein zu glauben, dass Computer so schnell sind, dass kein Berechnungsproblem außer ihrer Reichweite liegt.

Dieser Glaube ist falsch. Einige Berechnungsprobleme sind von Natur aus so komplex, dass – obwohl Algorithmen zu ihrer Lösung existieren – kein Computer auf der Erde heute schnell genug ist, um diese Algorithmen für auch nur mittelgroße Eingaben innerhalb einer Menschenlebens – oder sogar innerhalb der Lebensdauer der Erde selbst – vollständig auszuführen.

Um das weiter zu erläutern, stellen wir das Ganzzahl-Faktorisierungsproblem vor.

Ganzzahl-Faktorisierung

Eingabe: eine ganze Zahl N≥2N\geq 2
Ausgabe: die Primfaktorzerlegung von NN

Unter der Primfaktorzerlegung von NN verstehen wir eine Liste der Primfaktoren von NN und der Potenzen, auf die sie erhöht werden müssen, um NN durch Multiplikation zu erhalten. Zum Beispiel sind die Primfaktoren von 1212 die Zahlen 22 und 33, und um 1212 zu erhalten, muss man das Produkt von 22 hoch 22 und 33 hoch 11 bilden.

12=22⋅312 = 2^2 \cdot 3

Bis auf die Reihenfolge der Primfaktoren gibt es für jede positive ganze Zahl N≥2N\geq 2 genau eine Primfaktorzerlegung – eine Tatsache, die als Fundamentalsatz der Arithmetik bekannt ist.

Einige einfache Code-Demonstrationen in Python sind hilfreich, um die ganzzahlige Faktorisierung und andere damit zusammenhängende Konzepte weiter zu erklären. Für diese Demonstrationen werden folgende Importe benötigt.

# Added by doQumentation — required packages for this notebook
!pip install -q sympy
import math
from sympy.ntheory import factorint

Die Funktion factorint aus dem symbolischen Mathematikpaket SymPy für Python löst das ganzzahlige Faktorisierungsproblem für jede gewählte Eingabe NN. Wir können zum Beispiel die Primfaktorzerlegung von 12 erhalten, die natürlich mit der obigen Zerlegung übereinstimmt.

N = 12
print(factorint(N))
{2: 2, 3: 1}

Die Faktorisierung kleiner Zahlen wie 1212 ist einfach, aber wenn die zu faktorisierende Zahl NN größer wird, wird das Problem schwieriger. Das Ausführen von factorint auf einer deutlich größeren Zahl verursacht zum Beispiel eine kurze, aber merkliche Verzögerung auf einem typischen Personalcomputer.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))
{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

Für noch größere Werte von NN wird es unmöglich schwierig, soweit wir wissen. Die RSA Factoring Challenge, die von RSA Laboratories von 1991 bis 2007 durchgeführt wurde, bot beispielsweise einen Geldpreis von 100.000 Dollar für die Faktorisierung der folgenden Zahl, die 309 Dezimalstellen hat (oder 1024 Bits in Binärdarstellung). Der Preis für diese Zahl wurde nie gewonnen und ihre Primfaktoren sind bis heute unbekannt.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Es lohnt sich nicht, factorint auf RSA1024 anzuwenden – das würde unser Leben nicht überdauern.

Der schnellste bekannte Algorithmus zur Faktorisierung großer ganzer Zahlen ist das sogenannte Zahlkörpersieb (Number Field Sieve). Als Beispiel für die Verwendung dieses Algorithmus wurde die RSA-Challenge-Zahl RSA250, die 250 Dezimalstellen hat (oder 829 Bits in Binärdarstellung), im Jahr 2020 mithilfe des Zahlkörpersiebs faktorisiert. Die Berechnung erforderte Tausende von CPU-Kernjahren, verteilt auf Zehntausende von Maschinen auf der ganzen Welt. Wir können diese Leistung würdigen, indem wir die Lösung überprüfen.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)
True

Die Sicherheit des RSA-Public-Key-Kryptosystems basiert auf der Berechnungsschwierigkeit der ganzzahligen Faktorisierung, in dem Sinne, dass ein effizienter Algorithmus für die ganzzahlige Faktorisierung das System brechen würde.

Betrachten wir als Nächstes ein verwandtes, aber sehr unterschiedliches Problem: die Berechnung des größten gemeinsamen Teilers (ggT) zweier ganzer Zahlen.

Größter gemeinsamer Teiler (ggT)

Eingabe: nichtnegativer ganzer Zahlen NN und MM, von denen mindestens eine positiv ist
Ausgabe: der größte gemeinsame Teiler von NN und MM

Der größte gemeinsame Teiler zweier Zahlen ist die größte ganze Zahl, die beide ohne Rest teilt.

Dieses Problem ist mit einem Computer leicht lösbar – es hat in etwa die gleichen Berechnungskosten wie die Multiplikation der beiden Eingabezahlen. Die Funktion gcd aus dem Python-Modul math berechnet den größten gemeinsamen Teiler von Zahlen, die erheblich größer als RSA1024 sind, im Handumdrehen. (Tatsächlich ist RSA1024 der ggT der beiden Zahlen in diesem Beispiel.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Das ist möglich, weil wir sehr effiziente Algorithmen zur Berechnung von ggT haben, von denen der bekannteste der Euklidische Algorithmus ist, der vor über 2.000 Jahren entdeckt wurde.

Könnte es einen schnellen Algorithmus für die ganzzahlige Faktorisierung geben, den wir noch nicht entdeckt haben, der es ermöglicht, große Zahlen wie RSA1024 im Handumdrehen zu faktorisieren? Die Antwort lautet ja. Obwohl man erwarten könnte, dass ein effizienter Algorithmus für die Faktorisierung, der so einfach und elegant ist wie Euklids Algorithmus für die ggT-Berechnung, inzwischen entdeckt worden wäre, schließt nichts die Existenz eines sehr schnellen klassischen Algorithmus für die ganzzahlige Faktorisierung aus – abgesehen davon, dass wir bisher keinen gefunden haben. Einer könnte morgen entdeckt werden – aber halte nicht den Atem an. Generationen von Mathematikern und Informatikern haben gesucht, und die Faktorisierung von Zahlen wie RSA1024 bleibt außerhalb unserer Reichweite.