Miller-Rabin Primzahl-Test - kurz: MRT

Letztmalig dran rumgefummelt: 10.05.23 13:21:59

	Verschlüsselungen wie RSA setzen auf große Primzahlen, um sichere Schlüssel zu erstellen. Es ist aber gar nicht so leicht, Primzahlen in der geeigneten Größenordnung zu finden. Daher benutzen RSA-Implementierungen den Miller-Rabin-Primzahltest.
	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 Miller-Rabin-Test 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%).
	... mit Anmeldung für CHIP-Leser: https://www.heise.de/select/ct/2023/1/2223415045344186884
	Primzahl-Produkte

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.
	https://www.heise.de/select/ct/2023/1/softlinks/ysh6?wt_mc=pred.red.ct.ct012023.136.softlink.softlink

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.
	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!!!

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.
	Zahlenteiler Teilerproblem die Primzahl-Faktorierung

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 29. April 2023 um 4.22 Uhr