Fermat-Transformierung oder: Fermat's großer Satz

Letztmalig dran rumgefummelt: 21.06.26 18:58:59

	Die 129stellige Zahl 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541 ist Produkt zweier Primzahlen. Wie lauten diese Faktoren?
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren   Logo für den FERMAT'schen Großen Satz Wissen für Fortgeschrittene der Informatik Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???

1. Problembeschreibung

	We
	... ein Vorrat sehr großer Primzahlen                 FERMAT's großer Satz   FERMAT's großer Satz nach Tobias Hartnick

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Der nachfolgend beschriebene Algorithmus funktioniert nur für ungerade Primzahlprodukte genau zweier Zahlen und auch nur für Primzahlen, deren Abstand nicht zu groß ist, ansonsten wird das Verfahren extrem zeitkomplex.
	... das Fermatverfahren für ungerade Zahlen ... und das hat sich Fermat vor 350 Jahren einfallen lassen1 Rechenbeispiel FERMAT EXCEL-Rechenblatt  Sichere Passworte mit Public-Key-Verfahren   Faktorisierung nach Fermat - der Algorithmus ...   ... das Rechenbeispiel nach Fermat mit 2027651281   ... wir verwenden EXCEL und bauen uns ein Rechneblatt ... wir verwenden EXCEL und bauen uns ein Rechneblatt   Public Key Verfahren ...

3. Lösungsalgorithmen

	Dn.
	... das Schatztruhenproblem   Lösungsansatz 1       das Schatztruhenproblem zum ersten ... das Schatztruhenproblem zum ersten ...   das Schatztruhenproblem zum zweiten ... das Schatztruhenproblem zum zweien ...     ... die Sache mit der Schatztruhe

4. Programmvorschläge

	Hier nun gibt es zwei Angebote mit jeweil deutlich Einschränkungen: Variante eins arbeitet nach klassischem Fermat-Satz zur Primzahlfaktorisierung für Produkte von genau zwei Primzahlen und ist damit für einen großen Bereich und für kleine Abstände der Faktoren auch hinreichend schnell Große Abstände werden deutlich laufzeitkritisch. Einzige Einschränkung: funktioniert nur für uungerade Primzahlprodukte unter der Voraussetzung, dass die Eingabe auch wirklich das Produkt zweier Primzahlen ist. Das stellt aber keine wirkliche Einschränkung dar, da das Produkt zweier ungerader Zahlen immer ungerade ist. Alle geraden Produkte haben als einen Faktor ausnahmslos 2! Version zwei dagegen bietet Funktionalität für alle Eingaben - bringt aber den Vorrat an Primzahlen mit und schränkt so den Bereich der möglichen Faktoren drastisch ein - maximal unter einer Million für einen Faktor. Für alltägliche Belange dürfte das aber immer noch hinreichend sein - auch wieder unter dem Vorbehalt, dass die beiden Faktoren nicht zu weit auseinander liegen, ansonsten kommt noch das Laufzeitkriterium dazu.
	das Wurzel Ziehen klappt schon ...

5. Zusammenfassung

Angriff auf den Drucker der Firma BROTHER - tatsächlich funktioniert diese Faktorisierungsmethode immer für ungeraden n -allerdings können selbst Computer sie nur dann schnell genug ausführen, wenn die beiden Primfaktoren von n nicht zu weit auseinanderliegen, also ungefähr die gleiche Größenordnung haben. Und genau hier lag das Problem, das der Informatiker Hanno Böck in einer Programmbibliothek aufdeckte, die verschiedene Firmen nutzten: Die für die Verschlüsselung erzeugten Primzahlen waren nicht zufällig genug. Das Programm wählte oftmals zwei Primzahlen aus, die nah beieinander sind. Damit lässt sich die Faktorisierung von Fermat zum Aushebeln der Verschlüsselung nutzen ein Fakt, der eigentlich schon lange bekannt war. Böck erkannte, dass die Drucker bestimmter Firmen solche mangelhaften Verschlüsselungen verwendeten. Diese greifen auf RSA-Kryptografie zurück, um beispielsweise vertrauliche Unterlagen zu schützen, die durch ein Netzwerk an den Drucker geschickt werden. Jetzt bleibt nur zu hoffen, dass diese und auch andere Firmen die Sicherheitslücken geschlossen haben. Ohnehin werden viele Unternehmen ihre Verschlüsselungsstandards in den kommenden Jahren überdenken müssen: Denn auch wenn gewöhnliche Rechner an der Faktorisierung großer Zahlen scheitern, wird das bei leistungsfähigen Quantencomputern anders sein. Diese greifen bei der Berechnung allerdings auf komplizierte Prinzipien der Quantenmechanik zurück, von denen Fermat vor mehr als 350 Jahren definitiv noch nichts wissen konnte. (Spektrum.de, 21.03.2025)

6. Weiterführende Literatur

7. Links zum Thema

	http://www.mathematische-basteleien.de/kaprekarzahl.htm

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 14. Juni 2026 um 13.26 Uhr