Die Aufgabe: Schreiben Sie die Zahl 2015 als Produkt dreier natürlicher Zahlen. Wie viele unterschiedliche Lösungen existieren? Zwei Lösungen, die durch das blosse Vertauschen von Faktoren entstanden sind, sollen nicht als unterschiedliche Lösungen gelten.
Die Lösung: Wer alle Darstellungen einer natürlichen Zahl als Produkt von zwei oder mehr natürlichen Zahlen sucht, sollte zuallerest alle Primfaktoren finden, die in der Zahl stecken. Eine Primzahl ist nur durch 1 und sich selbst teilbar. Jede natürliche Zahl ist entweder eine Primzahl oder das Produkt aus mindestens zwei Primzahlen.
Ein Primfaktor von 2015 ist das auf jeden Fall die 5. Denn die Zahl endet auf eine 5 und muss daher zwingend durch 5 teilbar sein. 2015 dividiert durch 5 ergibt 403 - und 403 selbst ist keine Primzahl, wie ein kurzer Blick in eine Primzahltabelle zeigt.
Deshalb muss sich 403 in mindestens zwei weitere Faktoren zerlegen lassen. Bevor Sie anfangen herumzuprobieren - es gibt diverse Webseiten, die eine Zahl auf Knopfdruck in ihre Primfaktoren zerlegen. Zum Beispiel diese, diese und diese. 403 ist demnach das Produkt aus 13 und 31. Das sind beides Primzahlen, die nicht weiter zerlegt werden können.
Fassen wir zusammen: 2015 ist das Produkt 5*13*31, wobei alle drei Zahlen Primzahlen sind. Damit haben wir auf jeden Fall schon mal eine Lösung der Aufgabe gefunden. Doch es gibt noch mehr.
Warum? Die Zahl 1 ist ebenfalls eine natürliche Zahl. Damit ergeben sich gleich drei weitere Lösungen. Einer der drei Faktoren ist die 1, der zweite einer der drei Primfaktoren 5, 13, oder 31 und der dritte Faktor ist das Produkt der verbliebenen zwei Primfaktoren. Wir erhalten:
Doch bei vier Lösungen ist immer noch nicht Schluss. Schliesslich kann man den Faktor 1 ja auch zweimal nehmen: 1*1*2015. Also gibt es insgesamt fünf Lösungen:
Noch ein paar Anmerkungen zur Primzahlzerlegung: Man sieht einer natürlichen Zahl im Allgemeinen leider nicht an, ob sie eine Primzahl ist oder in welche Faktoren man sie zerlegen kann. (Abgesehen von einfachen Fällen wie einer 0, 2 oder 5 an der letzten Stelle). Bei der Suche nach den Primfaktoren einer Zahl muss mal letztlich ausprobieren - und für grosse Zahlen geht das nur mit Hilfe von Computern.
Deshalb eignen sich Primzahlen sehr gut zum Verschlüsseln. Das weit verbreitete RSA-Verfahren beispielsweise benötigt zwei grosse Primzahlen. Diese haben in der Regel mehr als 300 oder sogar mehr als 600 Stellen. Das Produkt der beiden großen Primzahlen ist Teil des öffentlichen RSA-Schlüssels, der zum Beispiel auf dem Server einer Webseite gespeichert ist. Ein Internetbrowser nutzt diesen frei herunterladbaren Schlüssel, um Daten vor der Übertragung zum Server zu chiffrieren - erkennbar am «https» in der Adresszeile.
Zum Entschlüsseln muss man die beiden ursprünglichen Primzahlen kennen - sie sind Teil des privaten Schlüssels, der in einem geschützten Bereich des Servers gespeichert ist. Das RSA-Verfahren beruht letztlich darauf, dass man zwei Mammutprimzahlen leicht miteinander multiplizieren kann, die Primfaktoren einer grossen Zahl sich hingegen nur schwer ermitteln lassen.
Die Primfaktorzerlegung einer 600- oder 1200-stellige Zahl ist selbst mit Supercomputern in überschaubarer Zeit kaum zu schaffen. Um der ständig steigenden Rechenpower standzuhalten, können RSA-Schlüssel zudem immer wieder verlängert werden, was den Aufwand beim Knacken weiter erhöht. Damit sind Angriffe eigentlich ausgeschlossen. Trotzdem hat es der US-Geheimdienst NSA geschafft, die RSA-Verschlüsselung auszuhebeln. NSA-Experten konnten die Menge der bei RSA genutzten Primzahlen künstlich verkleinern und musste somit nur vergleichsweise wenige Zahlen ausprobieren, um einen Schlüssel zu knacken.
Falls du die Rätsel der vergangenen Wochen verpasst hast - das sind die Links:
