Emmanuel Breuillard und Péter
Varjú von der University of Cambridge
haben sich ein Jahr später dagegen
mit allgemeinen Polynomen beschäf-
tigt. In ihrer erstaunlichen Arbeit
bestätigten sie dadurch eine 25 Jahre
alte Vermutung, die handfeste Folgen
für ein weit verbreitetes Verschlüsse-
lungsverfahren hat.
Schon 1993 mutmaßten der Mathe-
matiker Andrew Odlyzko von der Uni-
versity of Minnesota und sein Kollege
Bjorn Poonen, der heute am Massa-
chusetts Institute of Technology
arbeitet, dass reduzible Polynome mit
wachsender Komplexität im Meer der
Primpolynome untergehen. Zu diesem
Schluss führte sie eine simple Über-
legung. Primzahlen sind unter den
kleinen Zahlen weit verbreitet, werden
danach aber immer seltener. Das liegt
daran, dass die Liste der möglichen
Teiler für große Zahlen immer länger
wird. Bei Polynomen ist das anders.
Zum Scheitern verurteilt
Damit ein Polynom faktorisierbar ist,
müssen seine Koeffizienten im richti-
gen Verhältnis zueinander stehen.
x 2 + 5 x + 6 kann beispielsweise zu
zwei Faktoren (x + 3) und (x + 2)
zerlegt werden, weil es zwei ganze
Zahlen 2 und 3 gibt, die addiert den
zweiten Koeffizienten 5 ergeben und
multipliziert den dritten (6) liefern.
Polynome mit zusätzlichen Termen
führen zu wesentlich mehr und kompli-
zierteren Bedingungen. Somit wird es
immer unwahrscheinlicher, dass es
Faktoren mit ganzzahligen Koeffizien-
ten gibt, die sie alle erfüllen.
Weil ein allgemeiner Beweis dieser
Vermutung außer Reichweite war,
beschränkten Odlyzko und Poonen ihr
Problem auf Polynome, deren Koeffizi-
enten lediglich die Werte null oder eins
haben. Doch selbst in vereinfachter
Form dauerte es 25 Jahre, bis ihr
Verdacht bestätigt wurde – unter der
Bedingung, dass die berühmte rie-
mannsche Vermutung korrekt ist.
Breuillard und Varjú stießen durch
Zufall auf dieses Ergebnis. Denn sie
beschäftigten sich nicht direkt mit
Primpolynomen, sondern interessier-
ten sich für die Mathematik eines
»Random Walks«. Sie stellten sich
dabei eine Person auf einem Zifferblatt
vor, das gleichmäßig von eins bis elf
eingeteilt ist. Die Person steht am
Anfang auf der Eins und denkt sich
eine ganzzahlige Zahl x. Diese multipli-
ziert sie mit der Zahl, auf der sie steht,
und geht zu der entsprechenden Stelle
auf dem Zifferblatt. Dann wirft sie
eine Münze. Bei Zahl bleibt sie stehen,
bei Kopf geht sie noch einen Schritt
weiter. Dann beginnt der Vorgang vonNeuem: Multiplizieren der gedachten
Zahl x mit der Zahl, auf der sie steht,
Münzwurf und entsprechend eventuell
einen Schritt weiter gehen. Sobald ihr
Ergebnis größer als elf ist, läuft die
Person einfach rund um die Uhr wei-
ter, bis sie die erforderliche Anzahl an
Schritten erreicht hat. Solche »Uhren-
Mathematik« (so genannte modulare
Zahlensysteme) taucht in vielen Frage-
stellungen auf.Hintertür in der RSA-Verschlüsselung
Eines der wichtigsten heutigen Verschlüsselungsverfahren ist die RSA-
Verschlüsselung. Sie ähnelt dem denkbar einfachsten Codierungs-
schema: Man ordnet jedem Buchstaben einer geheimen Nachricht eine
Zahl zu und multipliziert diese mit einer zuvor vereinbarten Zahl. Um
den Code zu entschlüsseln, teilt man die Ziffernfolge einfach durch die
geheime Zahl.
Bei der RSA-Verschlüsselung führt ein Benutzer mit seiner Nachricht
mehrere Rechenschritte durch, unter anderem multipliziert er sie mit
einer sehr großen Zahl (Hunderte von Stellen lang). Um die Nachricht zu
entschlüsseln, muss man die Primfaktoren des entstandenen Produkts
herausfinden. Die Sicherheit dieser Methode beruht auf der Tatsache,
dass es keinen schnellen Weg gibt, um Primfaktoren großer Zahlen zu
berechnen.
Allerdings hat dieses Verfahren eine Hintertür. Jede Zahl lässt sich
eindeutig durch ein Polynom mit den Koeffizienten null und eins dar-
stellen; und während es schwierig ist, Zahlen zu faktorisieren, gibt es
effiziente Algorithmen, die ein Polynom in einfachere Bestandteile zer-
legen. Sobald man die Teiler eines Polynoms kennt, lassen sich daraus
die Primfaktoren der ursprünglichen Zahl bestimmen.
So funktioniert es:- Wählen Sie eine Zahl, zum Beispiel 15.
- Drücken Sie 15 in binäre Schreibweise aus: 1111 = 23 + 22 + 21 + 20.
- Verwandeln Sie diesen Ausdruck in ein Polynom, indem Sie die
Ziffern als Koeffizienten eines Polynoms behandeln: x3 + x2 + x + 1.
Für x = 2 entspricht dieses Polynom der Zahl 15. - Faktorisieren Sie das Polynom: (x2 + 1) ∙ (x + 1).
- Setzen Sie x = 2 in jeden dieser Faktoren ein: (22 + 1) = 5, (2 + 1) = 3.
Fazit: 5 und 3 sind die Primfaktoren von 15.
Dieser scheinbar komplizierte Weg, um die Teiler von 15 zu finden, er-
weist sich bei großen Zahlen als überaus nützlich. Wie der neue Beweis
von Breuillard und Varjú aber zeigt, ist die RSA-Verschlüsselung da-
durch nicht in Gefahr: Denn nicht jede faktorisierbare Zahl entspricht
einem reduziblen binären Polynom, wie das Beispiel 25 (= 24 + 23 + 1)
zeigt. x4 + x3 + 1 ist nämlich ein Primpolynom, obwohl 25 keine Primzahl
ist. Je größer ein Polynom, desto unwahrscheinlicher lässt es sich
zerlegen. Da die enorm großen Zahlen im RSA-Verfahren riesigen
Polynomen entsprechen, schwindet die Wahrscheinlichkeit, dass sie
faktorisierbar sind.