English
中文
Deutsch
Română
TürkçeTeilbarkeit und PrimzahlenGrößter gemeinsamer Teiler
Eine Architektin plant den Boden für einen großen Innenhof, der 18m x 30m misst. Sie möchte, dass er mit den größtmöglichen quadratischen Fliesen bedeckt ist, ohne Lücken oder Überlappungen an den Seiten. Welche Abmessungen haben diese Quadrate?
Die Fliesen haben eine Größe von
Wie zuvor geht es bei dieser Frage nicht um Geometrie, sondern um die Teilbarkeit. Die Länge der Seiten der Fliesen muss sowohl 18 als auch 30 teilen, und die größtmögliche Zahl die das erfüllt ist
Auch hier können wir mit der
18 | = | 2 | × | 3 | × | 3 | ||
30 | = | 2 | × | 3 | × | 5 | ||
Angenommen, X ist der ggT von 18 und 30, dann lässt sich 18 durch X teilen, weshalb die Primfaktoren von X auch 2, 3 und 3 beinhalten müssen. Außerdem lässt sich 30 auch durch X teilen, weshalb die Primfaktoren von X ebenso 2, 3 und 5 beinhalten müssen.
Um X zu finden, müssen wir einfach alle Zahlen multiplizieren, die Primfaktoren von 18
X = 2 × 3 = 6.
Jetzt haben wir eine einfache Methode, um den ggT von zwei Zahlen zu bestimmen:
- Mache die Primfaktorzerlegung für jede Zahl.
- Multipliziere die gemeinsamen Primfaktoren beider Zahlen.
Auch hier gilt für Primzahlen etwas Besonderes: Der ggT von zwei verschiedenen Primzahlen ist immer
Kryptographie
Eine der wichtigsten modernen Anwendungen von Primzahlen liegt in einem mathematischen Gebiet namens Kryptographie. Seit Jahrtausenden versuchen Menschen, Nachrichten irgendwie geheim zu halten, sodass nur der vorgesehene Empfänger sie lesen kann - das nennt man Verschlüsselung. Sie wird von allen genutzt, von Generälen, die geheime Befehle während des Krieges austauschen, bis hin zu persönlichen E-Mails oder Online-Banking-Details.
Die Menschen versuchten immer bessere und sicherere Verschlüsselungsmethoden zu entwickeln, aber nach einiger Zeit wurden sie alle mit noch fortschrittlicheren Algorithmen geknackt. Im Zweiten Weltkrieg nutzte die deutsche Wehrmacht die Enigma: eine komplexe Maschine, die aus einer Tastatur, rotierenden Walzen und Steckern bestand. Sie verschlüsselte Nachrichten mit einer von 158 Millionen Millionen Millionen Möglichkeiten (also 158 gefolgt von 18 Nullen!). Der Code galt allgemein als unknackbar, aber der britische Geheimdienst, angeführt vom Mathematiker Alan Turing, baute einige der ersten Computer, die es schafften, ihn zu entschlüsseln.
Deutsche Enigma-Maschine mit 4 Walzen
Die heutigen Computer sind viel fortschrittlicher und in der Lage, jede Sekunde Millionen von Möglichkeiten durchzuprobieren. Um bessere Verschlüsselungsalgorithmen zu entwickeln, muss man eine mathematische Operation finden, die selbst für leistungsfähige Computer schwierig ist: Computer sind unglaublich schnell bei Addition, Subtraktion, Multiplikation und Division. Wie sich jedoch herausstellt, sind Computer sehr langsam dabei, große Zahlen in Primzahlen zu zerlegen....
Demnächst - RSA-Beispiel mit Alice und Bob
Dieser Verschlüsselungsalgorithmus heißt RSA Verschlüsselung, nach seinen drei Erfindern Ron Rivest, Adi Shamir und Leonard Adleman, die ihn 1977 veröffentlichten. Es stellte sich heraus, dass dem britischen Geheimdienst seit 1973 eine sehr ähnliche Methode bekannt war, die aber lange Zeit geheim gehalten wurde.
Heute werden Primzahlen von Computern auf der ganzen Welt zum Austausch von Daten verwendet. Wenn du im Internet surfst oder Chat-Nachrichten sendest, erzeugt dein Telefon oder Laptop im Hintergrund große Primzahlen und tauscht öffentliche Schlüssel mit anderen Computern aus.