Die Primzahlfaktorisierung

Letztmalig dran rumgefummelt: 06.02.25 02:20:39

	Jede ganze positive Zahl verfügt über genau eine Zerlegung in Primfaktoren. Ich weiß nur noch, dass ich das in der Schule gutgehend gehasst habe, jeder mir damit auf die Ketten ging, aber auch jeder mir verschwiegen hat, warum ich das eigentlich wissen sollte. Nun gut - reichliche 40 Jahre später befasse ich mich mit Dingen, bei deren Lösungsverfahren ich aller furzlang über eben diesen Grundalgorithmus stoße. Ich ahne heute ganz langsam den Grund für das permanente Verweigern diesbezüglicher Aussagen durch Mathematiker: sie hatten keine Ahnung, was man damit machen kann. Dumm ist, dass zu heutiger Zeit wichtige Verschlüsselungsalgorithmen eben mit genau diesem Verfahren arbeiten - wir nennen das heute nur Einwegfunktionen - und dass diese es in sich haben, wissen die Mathematiklehrer von heute wiederum nicht ;-)
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Informationen - oder: wer braucht diesen Quatsch? 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für die Primzahlfaktorisierung begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Basiswissen der Informatik Wissen für Fortgeschrittene der Informatik
	Quellen: LOG IN - Heft 146/147 (2007) Seite 47 ff.

1. Problembeschreibung

	Es gibt keine Periodizität und kein Muster in den Primzahlen. Soviel ist sicher, der Anteil der Primzahlen unter den ersten N natürlichen Zahlen sinkt mit steigendem N. Unter den ersten 100 natürlichen Zahlen gibt es 25 Primzahlen (25%), unter den ersten 1000 sind es 168 (16.8%), unter den ersten 100000 sind es 9592 (9.6%) und unter den ersten 10 Millionen sind es 664759 Primzahlen (6.65%).
	das Feststellen, ob eine Zahl eine Primzahl ist, bis Wurzel 2 der Testzahl die Primzahl-Produkte Zeitkomplexität
	für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich - Beispiel: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 usw.

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

Für kleine Mengen M ist das Problem  in seiner Lösung empirisch durch Ausprobieren möglich! Für große Mengen existieren allerdings keine anderen Verfahren, als genau diese: ausprobieren jeden Elements mit jedem - das sind dann aber schon bei 10 Elementen 210 Möglichkeiten. Es sei denn, wir versuchen, neue Wege zu gehen und finden effizientere Algorithmen.

3. Lösungsalgorithmen

	Vom einfachsten Verfahren bis hin zu komplexer Mathematik ist alles möglich. Den Anfang machen simple Techniken, die für jeden einfach nachvollziehbar sind. Wir suchen die Primzahlen dadurch, dass wir der reihe nach durch alle Zahlen größer 2 und kleiner der Zahl selbst ganzzahlig dividieren. Ergibt sich bei keiner Division ein Rest von 0, so heben wir eine Primzahl gefunden. Danach verbessern wir schrittweise das Verfahren und zeigen auch neue Ideen auf.
	http://de.wikipedia.org/wiki/Pollard-p-1-Methode
	für große Zahlen gilt: Beginne mit n/2 (aufrunden, wenn n ungerade!) und bestimme von dort aus alle nächstgelegenen kleineren Primzahlen. Mit jeder gefunden Primzahlen wird beginnend bei round(n/2) ein quotient ermittelt. Lässt sich eine solche ganzzahlige Division mit Rest = 0 durchführen, so ist ein Faktor gefunden. Dies muss mit jeder gefunden Primzahl so lange durchgeführt werden, bis sich ein Rest verschieden von 0 ergibt.
	Eratosthenes von Kyene Pierre de Fermat kleiner Fermat'scher Satz oder auch kleiner Fermat

4. Programmvorschläge

	Hannes Uhlig hat kurzerhand ein auf dem programmierbaren Taschenrechner irgendwo gedownloadetes BASIC-Programm kurzerhand in Delphi umgeschrieben und wir haben uns erfolglos an die Aufgabe gemacht, den Quelltext in Denkstrukturen zurück zu übersetzen.
	Achtung - dies ist nur ein schlecht dokumentierter Tester - hilft aber vorerst auch schon weiter ;-) Primzahlfaktorisierung - oder auch: Primzahl-Zerlegung das Feststellen, ob eine Zahl eine Primzahl ist, ist vergleichsweise trivial auch für große Zahlen startbares Programm zum Ermitteln der Primzahlfaktoren auch für ziemlich große Zahlen

5. Zusammenfassung

6. Weiterführende Informationen - oder: wer braucht diesen Quatsch?

	War 'ne tolle Sache (zumindest für mich als Lehrer), einmal ein Schuljahr lang mit Schülern über doch die Grenzen von Programmiersprachen tangierende Probleme zu diskutieren, diese auszuloten, Algorithmen zu finden und wieder wegzuwerfen. Dümmer geworden ist dabei wahrscheinlich keine der betroffenen Seiten, die Schüler werden's teilweise einige Monate später an Universitäten bemerken ;-) Alles war im Rahmen des Möglichen: es anstrengend (was es ja sein soll), aber machbar - unten kann man einige Ergebnisse einsehen. Alles, was präsentiert wird, ist Wissensstand  Juni 2008 ;-)
	die Primzahlsuche die Zahlenteiler GGT KGV die Primzahlsuche - zumindest die ersten Beschreibungen sind trivial ;-) die Pseudoprimzahlen Quersummenermittlung
	die Primzahl-Zwillingssuche der Kaprekar Algorithmus die befreundeten Zahlen das 153-Problem - Narziß-Zahlen die Schmidtzahlen Pythagoräische Tripel Ulam-Spirale die Polynomzahlen Pascal-Zahlen die Goldbach-Vermutung das Palindrom Spiegelsummen-Problem die Perfect Numbers das Autoquadratzahlenproblem

7. Links zum Thema

	Obwohl von immenser Bedeutung für die gesamte Informatik, wird in der Literatur relativ wenig zu den Primzahlen ausgesagt und mit den angegebenen Beispielen und der Schulmathematik eher der Such nach den "kleinen" Primzahlen Rechnung getragen. Von enormer praktischer Bedeutung sind jedoch die großen Primzahlen.
	http://www.gm.nw.schule.de/~gymwiehl/prim/primfind.htm#KleinePrim
	http://www.matheprisma.uni-wuppertal.de/Module/Primz/

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 das 153-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 29. Mai 2008