In der vorliegenden Bachelorarbeit soll das große Spektrum der Primzahltests näher untersucht werden. Ziel soll es sein, ausgehend von ersten und einfachen Erkenntnissen, was die Definition von Primzahlen und allererste Ergebnisse auf diesem Gebiet umfasst, immer weiter vorzudringen. Schlussendlich soll ein verständlicher Weg aufgezeichnet sein, wie sich die Entwicklung von Primzahltest in unserer Gesellschaft immer weiter vollzogen hat. Zum Abschluss dieses Abschnittes wird der neueste Primzahltest, der im Jahre 2002 entdeckt wurde, stehen. Die AKS-Methode und der Algorithmus, den sie beinhaltet unterscheiden sich von den meisten bisherigen Tests mit Praxisbedeutung in seiner Determiniertheit. Diesen neuesten wissenschaftlichen Erkenntnissen auf dem Gebiet des Primalitätsproblems werde ich einen größeren Anteil meiner Arbeit widmen. Trotz allem nutzt der AKS-Algorithmus die Erkenntnisse seiner Vorläufer. So soll auch die Arbeit gestaltet sein, welche einen Überblick über die verschiedenen Tests und ihre Anwendung geben soll. Dabei werde ich mich vor allem auf das Buch "PRIMZAHLTESTS FÜR EINSTEIGER” von LASSE REMPE & REBECCA WALDECKER stützen.
In Bezug auf die Anwendbarkeit von Primzahltests in der Schule eignen sich meiner Ansicht nach die Siebmethoden für eine nähere Betrachtung. Der didaktische Bezug und dien Anwendung in der Schule, insbesondere der Frage inwieweit Primzahlen in der gymnasialen Oberstufe eine Rolle spielen, sollen den letzten Teil dieser Arbeit darstellen. Hierbei soll noch einmal aufgegriffen werden, inwieweit Primzahlen und die Bestimmung einer Zahl als Primzahl Anwendung in der Schule finden, und an welchen Stellen sich eine
sinnvolle didaktische Eingliederung anbietet. Auch welche anderen Tests sich aus meiner Sicht besonders für eine verständliche Betrachtung in der Schule eignen, soll dabei noch einmal eine Rolle spielen.
In der gesamten Arbeit wird die Effizienz und Alltagsrelevanz der verschiedenen Primzahltests immer wieder betrachtet. Die Bewertungen werden sich aus eigenen Reflexionen und wissenschaftlichen Meinungen ergeben. Um die Notwendigkeit von Primzahltests und somit den Sinn dieser Arbeit, wird es sich in dem ersten Teil drehen. In diesem werde ich allgemein die heute bedeutendste Anwendung der Primzahlen, genau benannt in der Kryptologie, kurz vorstellen. Hierbei gehe ich noch einmal gesondert auf das RSAVerfahren ein, welches auch meinen ersten Berührungspunkt mit der Kryptologie darstellt.
Inhaltsverzeichnis
1 Einleitung
1.1 Definition
1.2 Kryptologie
1.2.1 RSA-Verfahren
2 Primzahltests
2.1 Probedivision
2.2 Siebmethoden
2.2.1 SIEB DES ERATOSTHENES
2.2.2 SIEB VON ATKIN
2.2.3 Weitere Siebmethoden
2.3 Probabilistische Primzahltests
2.3.1 FERMAT-Test
2.3.2 SOLOVAY-STRASSEN-Test
2.3.3 MILLER-RABIN-Test
2.4 Primzahltests beruhend auf dem kleinen Satz von FERMAT
2.4.1 LUCAS-Test
2.4.2 PÉPIN-Test
2.4.3 LUCAS-LEHMER-Test
2.5 AKS-Methode
2.5.1 Ausgangspunkt der AKS-Methode
2.5.2 Die Grundstruktur des AKS-Algorithmus
2.5.3 Der AKS-Algorithmus
3 Anwendung in der Schule
3.1 Lehrplananalyse
3.2 Das SIEB DES ERATOSTHENES in der Schule
3.3 Potenziale anderer Primzahltests
4 Schluss
Zielsetzung & Themen
Die vorliegende Bachelorarbeit untersucht das umfangreiche Spektrum der Primzahltests, von einfachen Definitionen bis hin zu modernen, deterministischen Algorithmen. Das primäre Ziel ist es, die historische und methodische Entwicklung dieser Tests verständlich nachzuzeichnen, ihre Effizienz im Hinblick auf kryptologische Anwendungen zu bewerten und ihre didaktische Eignung für den Mathematikunterricht in der gymnasialen Oberstufe zu analysieren.
- Grundlagen der Zahlentheorie und die Definition von Primzahlen
- Kryptologische Relevanz, insbesondere das RSA-Verfahren
- Vergleich probabilistischer und deterministischer Primzahltests
- Der AKS-Algorithmus als revolutionärer, deterministischer Test
- Didaktische Konzepte zur Implementierung von Primzahltests in der Schule
Auszug aus dem Buch
2.5.3 Der AKS-Algorithmus
Um (1) aus dem letzten Unterkapitel zu zeigen, treffe ich - der Einfachheit halber - die folgende Vereinbarung für den Rest dieses Kapitels:
n ≥ 2 sei eine natürliche Zahl und p ein Primfaktor von n. Ist Q ein Polynom, so wird PQ als die Menge aller Polynome P bezeichnet, die folgende Bedingung erfüllen: (P (X))n ≡ P (Xn) (mod p, Q).
Ist n eine Potenz von p, so gehört, unabhängig von Q, jedes Polynom zu PQ. Zu zeigen ist also, dass bei Wahl eines geeigneten Q die Menge PQ nicht über alle Maßen groß ist und effizient ein Polynom gefunden werden kann, welches nicht Element von PQ ist. Das heißt natürlich nichts weiter, als dass der Satz von AGRAWAL, KAYAL und SAXENA bewiesen werden muss:
Es sei r eine zu n teilerfremde Primzahl mit ordr(n) > 4(log n)2 und Q := Xr − 1. Ist n keine Potenz von p, so gibt es weniger als r Polynome der Form P = X + a mit 0 ≤ a < p, die (P (X))n ≡ P (Xn) (mod p, Q) erfüllen.
Die Aussage des Satzes heißt also: wird eine Zahl r mit den geforderten Eigenschaften gefunden, so dass r höchstens polynomiell mit log n wächst, dann müssen nur noch r verschiedene Zahlen a überprüft werden, ob (P (X))n ≡ P (Xn) (mod p, Q) gilt. Ist dies für mindestens ein a nicht der Fall, so ist n zusammengesetzt, anderenfalls muss n prim sein oder eine Primzahlpotenz.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Thematik der Primzahltests ein und erläutert die Motivation der Arbeit, die sich auf die Bedeutung von Primzahlen für die moderne Kryptologie stützt.
2 Primzahltests: Dieses Kapitel bietet eine tiefgehende Analyse verschiedener mathematischer Verfahren zur Primalitätsprüfung, unterteilt in probabilistische Methoden und den deterministischen AKS-Algorithmus.
3 Anwendung in der Schule: Hier wird untersucht, wie Primzahltests in den Lehrplänen der deutschen Bundesländer verankert sind und wie diese komplexen Themen didaktisch sinnvoll im Unterricht vermittelt werden können.
4 Schluss: Das Abschlusskapitel reflektiert den erarbeiteten Überblick über das Thema und fasst die gewonnenen Erkenntnisse zur Anwendung von Primzahltests in Theorie und Praxis zusammen.
Schlüsselwörter
Primzahl, Primzahltest, Kryptologie, RSA-Verfahren, Sieb des Eratosthenes, Probabilistischer Primzahltest, Deterministischer Primzahltest, AKS-Algorithmus, Zahlentheorie, Primalität, Fermat-Test, Miller-Rabin-Test, Didaktik, Mathematikunterricht, Lehrplan
Häufig gestellte Fragen
Worum geht es in dieser Bachelorarbeit grundsätzlich?
Die Arbeit bietet eine fundierte Übersicht über Primzahltests, beleuchtet deren mathematische Grundlagen sowie deren Anwendung, insbesondere in der modernen Kryptologie, und diskutiert Möglichkeiten der didaktischen Aufarbeitung für den Schulunterricht.
Was sind die zentralen Themenfelder der Arbeit?
Die zentralen Felder umfassen die mathematische Klassifizierung von Primzahltests (probabilistisch vs. deterministisch), die Relevanz dieser Verfahren für die IT-Sicherheit durch das RSA-Verfahren und die schulische Vermittlung zahlentheoretischer Inhalte.
Was ist das primäre Ziel oder die Forschungsfrage?
Ziel ist es, ein Verständnis für die Effizienz und Funktionsweise verschiedener Primzahltests zu entwickeln und aufzuzeigen, wie diese komplexen Verfahren für den Mathematikunterricht in der Oberstufe adaptiert werden können.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit basiert auf einer Literaturanalyse und einer systematischen Aufarbeitung mathematischer Algorithmen sowie deren didaktischer Reflexion im Kontext geltender Lehrpläne.
Was wird im Hauptteil behandelt?
Im Hauptteil werden diverse Testverfahren wie die Probedivision, Siebmethoden (Eratosthenes, Atkin), probabilistische Tests (Fermat, Solovay-Strassen, Miller-Rabin) und schließlich der moderne, deterministische AKS-Algorithmus detailliert mathematisch beschrieben.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit wird durch Begriffe wie Primzahl, AKS-Algorithmus, Kryptologie, Siebverfahren und didaktische Vermittlung charakterisiert.
Warum wird dem AKS-Algorithmus ein besonderer Stellenwert eingeräumt?
Der AKS-Algorithmus nimmt eine Sonderstellung ein, da er als erster deterministischer Primzahltest mit polynomialer Laufzeit gilt und somit eine theoretisch wie praktisch revolutionäre Lösung für ein jahrzehntealtes mathematisches Problem darstellt.
Wie bewertet die Autorin die Anwendung des Siebs des Eratosthenes im Schulunterricht?
Das Sieb wird aufgrund seiner Einfachheit und visuellen Nachvollziehbarkeit als hervorragender Einstieg in die Zahlentheorie bewertet, der sowohl leistungsstarke als auch schwächere Schüler motivieren kann.
- Arbeit zitieren
- Karina Kliemank (Autor:in), 2011, Primzahltests, München, GRIN Verlag, https://www.grin.com/document/231584
