Die Primzahlfaktorisierung history menue Letztmalig dran rumgefummelt: 19.12.08 10:05:59

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 history menue scroll up

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%).
 

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 history menue scroll up

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 history menue scroll up
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 history menue scroll up

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 trivial auch für große Zahlen

startbares Programm zum Ermitteln der Primzahlfaktoren auch für ziemlich große Zahlen

 


5. Zusammenfassung history menue scroll up

 
 


6. Weiterführende Informationen - oder: wer braucht diesen Quatsch? history menue scroll up

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 history menue scroll up

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 history menue scroll up

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

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)