Lösung des Rätsels der Woche Diese Faktoren stecken in 2015

Die Jahreszahl 2015 hat es in sich. Das zeigt sich spätestens, wenn man versucht, sie in ein Produkt aus drei natürlichen Zahlen zu zerlegen.

Neues Jahr, neues Glück: Wie viele Zerlegungen finden Sie?
SPIEGEL ONLINE

Neues Jahr, neues Glück: Wie viele Zerlegungen finden Sie?

Von


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 bloße 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:

  • 1*5*403 (403=13*31)
  • 1*13*155 (155=5*31)
  • 1*31*65 (65=5*13)

Doch bei vier Lösungen ist immer noch nicht Schluss. Schließlich kann man den Faktor 1 ja auch zweimal nehmen: 1*1*2015. Also gibt es insgesamt fünf Lösungen:

SPIEGEL ONLINE

Vote
Rätsel der Woche

Wie schwer fanden Sie das Rätsel mit der Jahreszahl 2015? Bitte geben Sie den Schwierigkeitsgrad in einer Skala von 1 (sehr leicht) bis 5 (sehr schwer) an.

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 große 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 große 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 großen 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 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 Sie die Rätsel der vergangenen Wochen verpasst haben - das sind die Links:

hda

insgesamt 14 Beiträge
Alle Kommentare öffnen
Seite 1
swandue 02.01.2015
1. Folgeaufgabe: Bitte schreiben Sie alles in korrektem Deutsch
"Ein Primfaktor von 2015 ist das auf jeden Fall die 5." "NSA-Experten die Menge der bei RSA genutzten Primzahlen künstlich verkleinern und musste somit nur vergleichsweise wenige Zahlen ausprobieren, um einen Schlüssel zu knacken." Der Text wurde doch sicher schon vor Weihnachten vorbereitet, also hätte die Zeit eigentlich reichen müssen. ;-)
seltsam_ 02.01.2015
2. wenn 2015=a*b*c sein soll
wie kann dann in der letzten Lösung a=b ( beide sind 1). bitte klären sie mich auf
Stäffelesrutscher 02.01.2015
3.
Zitat von seltsam_wie kann dann in der letzten Lösung a=b ( beide sind 1). bitte klären sie mich auf
Es wurde nicht verlangt, dass es drei verschiedene natürliche Zahlen sein müssen. Im Rechenbeispiel 2*2*6 = 24 wird man nochmal mit der Nase darauf gestoßen.
jberner 02.01.2015
4. zu leicht
Von Mal zu Mal wird das Wochenrätsel banaler. Laaaangweilig!
dietert1 02.01.2015
5. Naja,
für mich war die Luft raus, als ich die drei Primfaktoren gefunden hatte. Interessant, dass 2015 tatsächlich nur drei Primfaktoren hat. Ich dachte, damit ist die Sache erledigt. Die RSA-Geschichte ist meineserachtens nur für den verständlich, der es eh schon wusste.
Alle Kommentare öffnen
Seite 1

© SPIEGEL ONLINE 2015
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH


TOP
Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.