Die Faktorisierung von FERMAT-Zahlen F_n = 2⁽²ⁿ⁾+1

machine à congruences

Im nunmehr zehnten Jahr seines Bestehens nimmt sich das TMSZ in seinem Osterworkshop 2005 der vornehmen Aufgabe an, natürliche Zahlen – so sie nicht selbst Primzahlen sind – in ihre nicht weiter zerlegbaren Bausteine, hinlänglich als Primfaktoren bekannt, zu zerlegen.

Eugène Olivier Carissan, constructeur

Zur Vermeidung einer initialen Bauchlandung hat das TMSZ-Team eine wahrlich extravagante, pikante Klasse von Zahlen ausgewählt, die sog. FERMAT-Zahlen. Dies ist sachlich notwendig, da es methodisch wenig sinnvoll ist, sich auf eine beliebig ausgewählte Zahl (einer sog. random number) zu stürzen und den Versuch der Zerlegung in ihre Primfaktoren  locker, flockig und entspannt zu starten.

Die Klasse der FERMAT-Zahlen bietet reichlich Gelegenheit zu zeigen, was man von einer speziellen Eingreiftruppe erwarten kann, geht es um die Frage, to be prime or not to be prime. Diese Zahlenklasse verlangt wahre Meisterschaft von ihrem Verehrer, will er sich im weltweiten Wettbewerb der Designer zahlentheoretischer Algorithmen Geltung, Ansehen und Respekt verschaffen.

Für Interessierte hier einige Informationen, die den Reiz zu einer vertiefenden Beschäftigung mit der Sache auslösen können bzw. sollen.

• Ausführungen zur Story der FERMAT-Zahlen

Henry Lehmers mechanische Faktorisierungs- maschine, Logik mit Fahradketten

Was sind das für Zahlen, die dem Primzahljäger nicht einfach ihre sämtlichen Primteiler auf  dem Tablett servieren, sondern die diese hüten wie eine Henne ihre Kücken? Wie ist man gerade auf diese Zahlen gestoßen? Weshalb weisen diese Zahlen diese besondere Eigenart auf? Man kann doch von einer Zahl nicht im Vorhinein sagen, ob sie schwierig zu faktorisieren sein wird oder nicht. – ? – Genau das ist falsch. Die FERMAT-Zahlen sind das wohl anspruchsvollste Beispiel für genau diese Aufgabe. Sie widersetzen sich penetrant und erfolgreich dem Versuch, ihre sämtlichen Primteiler zu ermitteln. FERMAT-Zahlen geben ihre Primteiler erst nach mühevollen Versuchen mit unvorstellbarem Rechenaufwand preis.

• Zur Faktorisierung von FERMAT-Zahlen

• Zur Geschichte der FERMAT-Zahlen

• Zur Gestalt von FERMAT-Zahlen

• Kann man das Problem der Faktorisierung von FERMAT-Zahlen nicht Computern überlassen?

• Und was nützt uns das Ganze?

Für Interessierte eine bescheidene Anzahl von Quellen im InterNet.

• Original announce of Complete factorization of the ninth Fermat number

• Geschichte der FERMAT-Zahlen

• Zum aktuellen Status

Einige FERMAT-Blitzlichter

• 1588-1648 Marin Mersenne

  glaubt mit 2⁶⁷-1 = 147.573.952.589.676.412.927 eine Primzahl gefunden zu haben.

• 1842-1891 Edouard Lucas

  gelingt der Nachweis, dass 2⁶⁷-1 das Produkt zweier Zahlen ist.

  Pikant: er kann die Faktoren nicht angeben.

• 1903 Frank Nelson Cole

  gibt die geglückte Faktorisierung der nicht-FERMAT-Zahl
  N:=2⁶⁷-1 = 193.707.721 x 761.838.257.287 bekannt.

  Frank Nelson Cole und der Zahl N geht es nach der erfolgten Sprengung den Umständen entsprechend gut.

  Man beachte, dass die Zahl 2⁶⁷-1 seit 1588 im Gespräch war! Ob die beiden gefundenen Faktoren ihrerseits wiederum Primzahlen waren, dies erhob sich zu einer neuen Frage. (by the way: sie sind es)

• 1970 Michael A.Morrison und John Brillhart

  gelingt die Zerlegung von F7 = 2¹²⁸+1 = p17 * p22, zwei 17- bzw. 22-stellige Primzahlen.

• 1975 John Brillhart

  behauptet in der renommierten Fachzeitschrift Mathematics of Computation, dass der Versuch der Faktorisierung einer 50-stelligen Zahl aussichtslos sei.

• 2005 Das TMSZ

  nimmt sich erstmalig des unbändigen Bedürfnisses zahlenhungriger Jüngerinnen und Jünger an, einige FERMAT-Zahlen zu faktorisieren.

  Möge die Übung gelingen.