Die Pseudoprimzahlen

Letztmalig dran rumgefummelt: 07.03.08 18:59:35

	Die Primzahlen sind Klassiker der Mathematik und auch für findige Algorithmen in der Informatik eine erste Adresse :-) International laufen sich Computer heiß, werden neue, und vor allem effizientere Algorithmen gesucht, welche die Forschung nach weiteren, vor allem sehr großen Primzahlen beschleunigen sollen und hoffen vor allem Kryptologen, dass dies nicht so schnell gelingen möge. Sehr große Primzahlen sind nämlich heutzutage die Basis aller als sicher geltenden Chiffrierungsalgorithmen.
	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 die Pseudoprimzahlen 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%).
	nun ist für Computer die Aufgabe, die ersten 1000 zu finden noch nicht gerade schwierig - es ist auch nicht schwierig, eine 100-stellige Zahl zu prüfen, ob sie den eine Primzahl sei - aber alle hundertstelligen zu finden, kann schon zeitkomplex werden 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.
	einfachster und rechenintensivster Primzahltester nach dem Bute-Force-Verfahren einfachster und rechenintensivster Primzahltester nach dem Bute-Force-Verfahren für die Suche großer Primzahlen ereichen wir schnell die Zeitkomplexität
	Achtung - dies ist nur ein Primzahltester - hilft aber vielleicht auch schon weiter ;-) das Feststellen, ob eine Zahl eine Primzahl ist, ist trivial auch für große Zahlen das Feststellen, ob eine Zahl eine Primzahl ist, ist trivial auch für große Zahlen

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.
	Methode 1: Einsatz purer dummer Gewalt - das ergibt aber immerhin für kleine Zahlen in vertretbarem Zeitaufwand vollkommen korrekte Lösungen:       Boolean-Test-Variable gefundende Primzahlen Zähler für Divisionen       false 2 0 3 3 : 2 = 1 Rest 1 false   1 4 4 : 2 = 2 Rest 0 true   2   4 : 3 = 1 Rest 1 true 3 3 5 5 : 2 = 2 Rest 1 false   4   5 : 3 = 1 Rest 2 false 5 5   5 : 4 = 1 Rest 1 false   6 6 6 : 2 = 1 Rest 1 false   7   6 : 3 = 2 Rest 0 true   8   6 : 4 = 1 Rest 2 true   9   6 : 5 = 1 Rest 1 true   10 7 7 : 2 = 3 Rest 1 false   11   7 : 3 = 2 Rest 1 false   12   7 : 4 = 1 Rest 3 false   13   7 : 5 = 1 Rest 2 false   14   7 : 6 = 1 Rest 1 false 7 15 8 8 : 2 = 4 Rest 0 false/true   16   8 : 3 = 2 Rest 2 true   17   8 : 4 = 2 Rest 0 true   18   8 : 5 = 1 Rest 3 true   19   8 : 6 = 1 Rest 2 true   19   8 : 7 = 1 Rest 1 true   20 9 9 : 2 = 4 Rest 1 false   21 Brute-Force-Angriffe for i:=2 to bereich do begin{begin of for1}   test:=false;{Annahme, dass aktuelle Zahl keine Primzahl}   for j:=2 to i-1 do   begin{begin of for2}     if i mod j=0     then     begin{begin of then}       test:=true;     end;{end of then}   end;{end of for2}   if test=false   then   begin{begin of then}     ListBox1.Items.Add(IntToStr(i))   end;{end of then} end;{end of for1} Brute-Force-Methode beim Herausfinden der ersten 37434 Primzahlen Brute-Force-Methode beim Herausfinden der ersten 37434 Primzahlen
	wir gehen nur bis zur Hälfte der Dividenden
	wir gehen nur bis zur Quadratwurzel der Dividenden
	wir tun das, was zwingend ist: wir verwenden zum Test nur die ungeraden Zahlen!!!
	Eratosthenes von Kyene Pierre de Fermat kleiner Fermat'scher Satz oder auch kleiner Fermat

4. Programmvorschläge

	Hannes Uhlig hat unser Vorschläge konsequent aufgegriffen und einschließlich der Problematik Oma und Katze ein Programm des Kaprekar-Algorithmus notiert, in welchem schon einige Kerngedanken eines sauberen - eben noch nicht objektorientierten Programmieirstils zusammenlaufen.

5. Zusammenfassung

6. Weiterführende Literatur

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 7. März 2008