Quelltext der Seite Diskussion:Miller-Rabin-Test

{{Redundanzhinweis|3=Algorithmus von Miller|4=Miller-Rabin-Test#Algorithmus|Beginn=Juli 2020|Diskussion=Wikipedia:Redundanz/Juli 2020/Archiv#Algorithmus von Miller - Miller-Rabin-Test#Algorithmus}}
Moin,
der Artikel ist wirklich nett und die unter http://home.arcor.de/rienhardt/files/miller_rabin.pdf angegebene PDF ist auch gut geschrieben. Aber in der PDF wird ein (zu einfacher) Beweis mit Hilfe eines gruppentheoretischen Ansatzes geführt. Der Beweis selbst ist zwar korrekt, liefert aber nur 1/2 als WS für einen Nicht-Zeugen je Durchlauf. Im Wiki-Text steht ja, dass es sogar 1/4 ist; kann man an der Stelle für den Weblink aber dennoch darauf hinweisen? Nicht, dass das bei unbescholtenen Lesern zu Verwirrungen führt.
Beste Grüße, Timm.

Ein Beweis steht z.B. in O. Forster, Algorithmische Zahlentheorie.



== n-1 als Basis? ==

Was bedeutet der Hinweis "0, 1 oder n-1 als Basis zu wählen, macht keinen Sinn"? Ich habe oft gelesen, dass die Basis nur <n sein muss. Was stimmt?
--[[Spezial:Beiträge/84.56.98.147|84.56.98.147]] 00:47, 28. Jan. 2008 (CET)

:In der Literatur findet man den Algorithmus sowohl mit <math>n-1</math> als Basis, als auch ohne. Deshalb habe ich den Hinweis entfernt. Ein Beispiel für den Algorithmus mit <math>n-1</math> findet sich in Buchmanns „Einführung in die Kryptographie“ und ein Beispiel ohne <math>n-1</math> im Buch „Prime Numbers“ von Crandall und Pomerance. --[[Benutzer:Stefan Birkner|Stefan Birkner]] 14:27, 18. Aug. 2008 (CEST)

== Prüfung auf Teilerfremdheit ==
a und n müssen zueinander Teilerfremd sein, da ansonsten der eigentliche Test (bei fehlender Teilerfremdheit) negativ ausfallen würde. --[[Benutzer:Arbol01|Arbol01]] 11:08, 30. Jun 2006 (CEST)

:Ich finde auf die Schnelle kein Beispiel, das deine Aussage untermauert. Kannst du eine Zahl nennen, bei der die Überprüfung der Teilerfremdheit notwendig ist? Welche Quelle verwendest du? --[[Benutzer:Squizzz|Squizzz]] 13:03, 30. Jun 2006 (CEST)

::Puh, ich dachte schon, ich würde es nicht finden: ''The new Book of Prime Number Records, Paolo Ribenboim, 1996, ISBN 0-387-94457-5'', Seite 113, D. Strong Pseudoprimes in Base a:
:::''Let n be an odd composite integer, let n - 1 = 2<sup>s</sup>d with d odd and s >= 1; let a be such that 1 < a < n, gcd(a,n)=1''
::Für die Primzahl ist das prinzipiell egal, da für jede Basis a teilerfremd zu n ist. Aber mit Miller-Rabin möchte man ja möglichst viele Pseudoprimzahlen ausschließen. Nebenbei ergibt sich ein Seiteneffekt. Wenn der Test auf die Teilerfremdheit von a und n negativ verläuft, hat man eine partielle Faktorisierung, auch wenn man danach nicht gesucht hat. --[[Benutzer:Arbol01|Arbol01]] 13:53, 30. Jun 2006 (CEST)

Die Prüfung auf Teilerfremdheit ist nicht notwendig. Wenn <math>a</math> und <math>n</math> nicht teilerfremd sind, dann ist
:<math>a^x \not\equiv \pm 1 \mod n</math>
und <math>a</math> wird deshalb als zusammengesetzte Zahl erkannt. --[[Benutzer:Squizzz|Squizzz]] 21:21, 1. Jul 2006 (CEST)

Ja, a und n müssen nicht teilerfremd sein, ABER: wenn (a,n)<>1, dann ist man fertig, und brauch den miller-rabin test erst gar nicht starten! 
--[[Benutzer:81.173.232.96|81.173.232.96]] 12:33, 4. Jul. 2007 (CEST)

== Satz von Miller ==

1. was soll das sein, der satz von miller?
2. im übrigen, müsst ihr euch hier ganz schön anstrengen, um das verfahren zu beschreiben. ihr habt leider stark-pseudoprim nur für zusammengesetzte zahlen definiert. auf primes.utm.edu ist stark-pseudoprim die eigenschaft an sich, die zahl ist dann entweder prim oder zusammengestzt. der vorteil ist, das rabin-miller-verfahren lässt sich dann in zwei sätzen beschreiben: (1) wähle eine zufällige basis a. (2) teste, ob n eine a-starke pseudozahl ist, (3) wiederhole das verfahren (so oft du willst). fertig. -- [[Benutzer:81.173.233.2|81.173.233.2]] 12:40, 9. Okt. 2006 (CEST)

:Den Hinweis auf einen Satz von Miller habe ich entfernt. Ich denke, dass es sich hierbei um das handelt, was ich unter Funktionweise hinzugefügt habe. --[[Benutzer:Stefan Birkner|Stefan Birkner]] 15:22, 18. Aug. 2008 (CEST)

== Weblink gelöscht ==

Ich habe den Weblink auf http://www.bitnuts.de/rienhardt/docs/miller_rabin.pdf gelöscht. Der Beweis ab S. 9, dass die Fehlerwahrscheinlichkeit höchstens <math>\frac{1}{2}</math> pro Schritt ist, ist meiner Meinung nach falsch. Im Beweis soll gezeigt werden, dass ein zusammengesetztes <math>n</math> höchstens <math>\frac{n-1}{2}</math> Entlastungszeugen hat. Dabei geht der Autor davon aus, dass <math>\mathbb{Z}_n^*</math> eine Gruppe ist, was aber genau für zusammengesetzte <math>n</math> falsch ist. --[[Benutzer:Floklk|Floklk]] 23:33, 15. Okt. 2006 (CEST)
: Meistens ist damit schon die [[prime Restklassengruppe]] gemeint, die in der Tat eine Gruppe ist. Allerdings ist ihre Ordnung nicht <math>n-1</math>, sondern <math>\phi(n)</math>, und damit ist der Schluss, dass es mindestens <math>\frac{n-1}2</math> ''Be''lastungszeugen gibt, falsch.--[[Benutzer Diskussion:Gunther|Gunther]] 23:43, 15. Okt. 2006 (CEST)
:: Ich habe den selben oder einen ähnlichen Beweis in Volker Heun: Grundlegende Algorithmen  (vieweg Verlag, Braunschweig 2000) gefunden. Dabei ist <math>\mathbb{Z}_n^*:=\{a\in\mathbb{Z}_n:ggT(a,n)=1\}</math>. Damit könnte es dann funktionieren... wenn in der pdf das aber nicht erwähnt ist, kommt man da von selber nicht wirklich drauf und damit lassen wir den Link denke ich lieber draußen. --[[Benutzer:Floklk|Floklk]] 17:00, 16. Okt. 2006 (CEST)
::: Habe mein Dokument überarbeitet und entsprechende Hinweise eingefügt. Danke für die konstruktive Kritik. Gruß Florian R.

ich möchte die autoren darauf aufmerksam machen, das der hier diskutierte link wieder online ist. und zum zweiten auf seite 10 immmer noch von einer abschätzung (n-1)/2 gesprochen wird. ich würde das löschen. --[[Benutzer:81.173.232.96|81.173.232.96]] 12:26, 4. Jul. 2007 (CEST)

== nicht null gelöscht ==

"Sie wird allerdings nie gleich null." nehmen wir n=3, dann ist a=2 einziger teilerfremder kandidat und mit einem test die fehlerwahrscheinlichkeitauf null. --[[Benutzer:84.44.131.176|84.44.131.176]] 01:42, 23. Nov. 2006 (CET)

== Das Selfridge schon 1974 dabei war nützt mir nichts wenn ich nicht weiß wann Rabin den Test veröffentlicht hat. OT ==

Das Selfridge schon 1974 dabei war nützt mir nichts wenn ich nicht weiß wann Rabin den Test veröffentlicht hat.

:Vielleicht findest du ja heraus, wann Miller und Rabin den Test veröffentlicht haben. -- [[Benutzer:Stefan Birkner|Stefan Birkner]] 00:13, 11. Feb. 2009 (CET)

== Deterministische Varianten ==

Habe eben den Abschnitt "deterministische Varianten" hinzugefügt. Meine Tastatur verfügt aber nicht über das sz, kann bitte jemand den Abschnitt entsprechend korrigieren? Dank im voraus. [[Benutzer:Gulliveig|Gulliveig]] 09:55, 25. Jun. 2009 (CEST)
:(Quote)>"Meine Tastatur verfügt aber nicht über das sz". '''Gibt es kein Ersatzzeichen ?''' Vielleicht bitte bei '''WIKIPEDIA:HILFE''' suchen. Eine wahre Fundgrube . [[Spezial:Beiträge/37.5.134.28|37.5.134.28]] 21:17, 8. Aug. 2013 (CEST)
::Es gibt auch das "ß" zum anklicken: '''Temporär''' alle Berechtigungen zulassen (Java Script und andere Scripte zeitweise erlauben.) Ganz unten befinden sich die gebräuchlichsten Sonderzeichen, die mit Mausklick auf die Eingabe "gezaubert" werden können. [[Spezial:Beiträge/37.5.134.28|37.5.134.28]] 22:14, 8. Aug. 2013 (CEST)

== Fehler bei den Zeugen ==
Wie die Herren Pomerance, Selfridge und Wagstaff sowie Jaeschke auf Ihren Schluss kommen, weiß ich nicht, jedenfalls sind 997.633, 1.024.651, 6.733.693, 10.024.561, 10.267.951 unter http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Carmichael-Zahlen als Carmichael-Zahl gelistet, werden aber mit den wenigen Zeugen trotzdem als Primzahl dargestellt, was offensichtlich (wenn die Liste nicht falsch ist...) falsch ist.  --[[Spezial:Beiträge/93.206.23.89|93.206.23.89]] 22:58, 5. Jan. 2012 (CET)Tofix

: Hmm? Was für'n Schluss? Für alle Zahlen unterhalb der ersten 2, 3 Grenzen kann man ohne clevere Dinge auf 'nem handelsüblichen PC ohne allzu große Wartezeit nachprüfen, dass Miller-Rabin mit den genannten Zeugen das selbe Ergebnis liefert wie z.B. Probedivision. Für die höheren Grenzen nimmt man dann eben Rechenzentren und schlauere Dinge als vollständigen Vergleich mit Probedivision.
: Die 5 Carmichael-Zahlen, die du nennst, erkennt eine Implementation, die ich hier herumliegen habe und für kleine Zahlen genau die angegebenen Grenzen und Zeugen benutzt, korrekt als nicht-Primzahl. --[[Benutzer:Daniel5Ko|Daniel5Ko]] 00:08, 6. Jan. 2012 (CET)

== Starke Pseudoprimzahlen ==

Den Satz

"Zahlen, bei denen der Miller-Rabin-Test immer „n  ist wahrscheinlich eine Primzahl“ ausgibt, obwohl sie keine Primzahlen sind, nennt man starke Pseudoprimzahlen."

hab ich rausgenommen, da er schlicht nicht stimmt. Eine zusammengesetzte Zahl n ist immer nur "Starke Pseudoprimzahl" bzgl. einer bestimmten Basis. Der Miller-Rabin-Test wird deshalb mit mehreren verschiedenen Basen durchgeführt. Nach k Versuchen ist also die Wahrscheinlichkeit, dass n nicht als zusammengesetzt erkannt wurde, nur noch 4^(-k). Mit anderen Worten: Es gibt keine zusammengesetzten Zahlen, die der Miller-Rabin-Test nicht als zusammengesetzt erkennen kann. <small>(''nicht [[Hilfe:Signatur|signierter]] Beitrag von'' [[Benutzer:137.226.57.88|137.226.57.88]] ([[Benutzer Diskussion:137.226.57.88|Diskussion]]&nbsp;|&nbsp;[[Spezial:Beiträge/137.226.57.88|Beiträge]]) 11:46, 5. Mär. 2010 (CET)) </small>

== 2 auch oder? ==

"wenn n < 9.080.191, ist es ausreichend a = 31 und 73 zu testen." <small>(''nicht [[Hilfe:Signatur|signierter]] Beitrag von'' [[Benutzer:Tompazi|Tompazi]] ([[Benutzer Diskussion:Tompazi|Diskussion]]&nbsp;|&nbsp;[[Spezial:Beiträge/Tompazi|Beiträge]]) 19:01, 13. Mär. 2010 (CET)) </small>
: Nein. Geht ohne 2. --[[Benutzer:Daniel5Ko|Daniel5Ko]] 00:08, 6. Jan. 2012 (CET)

== <math>n - 1 = d \cdot 2^j</math>  -> was ist J ? ==

Woher nehme ich die Zahl J ? Außerdem, einen Algorithmus kann man aus dieser unvollständigen Beschreibung partout nicht ableiten. [[Spezial:Beiträge/37.5.134.66|37.5.134.66]] 23:10, 4. Aug. 2013 (CEST)

: Da d ungerade sein soll, ist j der Exponent der größten Zweierpotenz, die n-1 teilt. --[[Benutzer:Daniel5Ko|Daniel5Ko]] ([[Benutzer Diskussion:Daniel5Ko|Diskussion]]) 23:37, 4. Aug. 2013 (CEST)
::Vielen Dank erst mal. Gibt es auch einen programmierbaren Algorithmus ?. MfG. Dank im Voraus. [[Spezial:Beiträge/37.5.134.28|37.5.134.28]] 22:06, 8. Aug. 2013 (CEST)

::: Ja, gibt's. Hier mal konkreter Code für eine deterministische Variante: (Wieviel davon tatsächlich aus dem Artikel ersichtlich ist, weiß ich gerade nicht, und bin auch zu faul, das zu prüfen.) 

<syntaxhighlight lang="Haskell">
import Control.Arrow

millerRabin :: Integer -> Bool
millerRabin 1 = False
millerRabin 2 = True
millerRabin n 
	| even n = False
	| otherwise = not $ any counter $ takeWhile (<n) as where
		counter a = 
			let x = modPow n a d in
			x /= 1 && x /= n-1 && rLoop (s-1) (x^2 `mod` n) where
					rLoop 0 _ = True
					rLoop r x
						| x == 1 = True
						| x == (n-1) = False
						| otherwise = rLoop (r-1) (x^2 `mod` n) 
		(s,d) = shift (n-1)
		shift x = case divMod x 2 of
			(x', 0) -> first (1+) $ shift x'
			_ -> (0, x)
		as 
			| n < 1373653 = [2,3]
			| n < 9080191 = [31,73]
			| n < 4759123141 = [2,7,61]
			| n < 2152302898747 = [2,3,5,7,11]
			| n < 3474749660383 = [2,3,5,7,11,13]
			| n < 341550071728321 = [2,3,5,7,11,13,17]
	 		| n < 3825123056546413051 = [2,3,5,7,11,13,17,19,23]
			| otherwise = error "Dunno!"
			
modPow md = (^) where
	_ ^ 0 = 1
	a ^ 1 = a `mod` md
	a ^ 2 = a `mod` md * a `mod` md
	a ^ n = a^n'^2 * a^d `mod` md where
		(n',d) = divMod n 2
</syntaxhighlight>


:::Eine Formulierung des Algorithmus für eine Basis a gibt es z.B. hier: [http://books.google.de/books?id=XLY9AnfDhsYC&pg=PA127#v=onepage&q&f=false]. Sowas könnte man meiner Meinung nach schon in den Artikel aufnehmen. Momentan ist das mit den Algorithmusteilen, Herleitungen und Beweisversuchen im Artikel schon etwas wirr.  -- [[Benutzer:HilberTraum|HilberTraum]] ([[Benutzer Diskussion:HilberTraum|Diskussion]]) 13:55, 9. Aug. 2013 (CEST)
::::'''Tausend Dank''' [[Spezial:Beiträge/37.5.134.87|37.5.134.87]] 00:00, 23. Aug. 2013 (CEST)

== Definition der verwendeten Modulo-Variante ==

Mir ist beim Lesen des Artikels unklar geblieben, wie der Rest errechnet wird. Es wird erwähnt, dass 
:<math>a^{d \cdot 2^r} \equiv -1 \mod n</math> 
für ein ''r'' mit ''0 &le; r < j''.

Aber wie kommt es überhaupt dazu, dass der Rest negativ wird, wenn man nur positive Zahlen prüft und nur positive Zahlen als Teiler hat. Eine klare Definition würde helfen. --[[Spezial:Beiträge/134.130.4.241|134.130.4.241]] 21:44, 21. Mär. 2015 (CET)

Ich finde einen negativen Modulo auch ungewöhnlich. Mit "-1 mod n" gemeint ist wohl "(n-1) mod n". Es wäre wohl klarer, wenn es auch so geschrieben würde (sowohl in der Formel als auch in den angegebenen möglichen Folgen des Miller-Rabin-Tests). Da ich aber kein Mathematiker bin, überlasse ich das Anderen. <small>(''nicht [[Hilfe:Signatur|signierter]] Beitrag von'' [[Spezial:Beiträge/93.135.190.207|93.135.190.207]] ([[Benutzer Diskussion:93.135.190.207|Diskussion]])<nowiki/> 02:05, 21. Mai 2015 (CEST))</small>

== <math> a^{p - 1}</math>  muss nicht mehr berechnet werden? ==

Ein sehr schöner Artikel!
Eine Sache verstehe ich leider nicht:
Im Teil "Funktionsweise" steht im letzten Satz, dass man sich am Schluss der Schleife die Berechnung von <math> a^{d \cdot 2^j}</math>, also dann <math> a^{p - 1}</math> sparen kann. Ich sehe aber gerade leider nicht den Grund dafür.
Könnte ich dann nicht zusaätzlich mit dem kleinen Satz von Fermat einen Zeugen dafür suchen, das n zusammengesetzt ist?

Vielleicht ist das ja was Offensichtliches, aber ich sehe es jedenfalls gerade nicht.
Wäre dankbar für eine Antwort.

:Man rechnet, bis entweder 0 oder 1 kommt, dann ist n keine Primzahl (außer die 1 steht schon an Anfang), oder bis n-1 kommt, dann kann n prim sein. Anderenfalls wird weitergerechnet, es sei denn man ist schon beim vorletzten Element <math>a^{2^{j-1}d}</math>. Dann kann n nicht prim sein, denn mit n prim muss als letztes Element 1 kommen und davor 1 oder n-1. --[[Benutzer:Megatherium|Megatherium]] ([[Benutzer Diskussion:Megatherium|Diskussion]]) 22:51, 17. Sep. 2017 (CEST)

== Laufzeit ==

Mir fehlen in dem Artikel noch Laufzeiten für den Algorithmus. Leider kann ich das zurzeit nicht ausreichend selbst beurteilen.

== Fehler im Abschnitt "Zuverlässigkeit" ==

Der Satz "Ist ''n'' ≥ 5 ungerade und nicht prim, so enthält die Menge { 2 , 3 , … , ''n'' − 2 } höchstens (''n'' − 3) / 4 Elemente ''a'' mit ggT ⁡ ( ''a , n'' ) = 1" ist falsch. Sei etwa ''p'' ≥ 3 eine Primzahl und ''n = p''<sup>2</sup>. Die Menge {2, … , ''n'' − 2 } besteht aus genau ''n'' - 3 Elementen, und von diesen sind genau die Zahlen ''p'', 2''p'', …, ''p''*(''p''-1) nicht teilerfremd zu ''n''. Folglich gibt es genau ''n - p '' - 2 > (''n'' - 3) / 4 Elemente in der angegebenen Menge, die teilerfremd zu ''n'' sind.

Was ist "''x''" in der Formel "'' a<sup>x</sup> ≡ k g'' ( mod ''n'' )"? [[Benutzer:Gandalf_Mithrandir|<span style="color: #BF00BF">Gandalf </span>]][[Benutzer Diskussion:Gandalf_Mithrandir|<span style="color: #BF00BF"> Mithrandir</span>]] 18:25, 10. Jun. 2018 (CEST)

: Hm, der Satz geht ja noch weiter: „…, die keine Zeugen für die Zusammengesetztheit von <math>n</math> sind.“ -- [[Benutzer:HilberTraum|HilberTraum]] (''[[BD:HilberTraum|d]], [[P:M|m]]'') 19:00, 10. Jun. 2018 (CEST)

Es gibt ''noch ein Fehler'' : statt 1/4^8 muss es heißen 1/4^s [[Spezial:Beiträge/170.133.12.82|170.133.12.82]] 11:50, 24. Jul. 2023 (CEST)

:Das stand da schon, allerdings war das 's' arg klein; hab' es in (1/4)^s geändert -- hoffentlich besser lesbar. --[[Benutzer:PaulSch|PaulSch]] ([[Benutzer Diskussion:PaulSch|Diskussion]]) 12:54, 24. Jul. 2023 (CEST)

== Fehler im Beipielcode? ==

Die angegebene Implementierung liefert für n=34214(!) und a=23469 als Ergebnis, dass n prim sei, obwohl es sich ja um eine gerade Zahl handelt... Ich habe die Berechnung noch nicht Schritt für Schritt nachverfolgt und weiß daher noch nicht, wo der Fehler entsteht, aber das Ergebnis ist konsistent bei Verwendung von drei verschiedenen Compilern auf 2 verschiedenen Betriebssystemen. --[[Spezial:Beiträge/82.207.245.194|82.207.245.194]] 12:57, 19. Nov. 2022 (CET)
:Der MRT ist nur für ungerade n anwendbar (s. Artikel). Das steht als Kommentar auch im Beispielcode: "// n ungerade, 1 < a < n-1"; allerdings wird diese Vorbedingung nicht überprüft. --[[Benutzer:PaulSch|PaulSch]] ([[Benutzer Diskussion:PaulSch|Diskussion]]) 13:32, 19. Nov. 2022 (CET)

== Test von fragwürdigem Nutzen ==

Der Test bringt im Vergleich zum Test von [[Euler]] keinen wesentlichen Vorteil. Ist die Zahl nach Euler keine Primzahl ergibt sich sogar gar kein Vorteil, weil alle Zahlen (mit negativem Ergebnis) getestet werden müssen. In den meisten Fällen ist die Zahl, bei großen Zahlen zumindest, keine Primzahl. Das Verfahren von Rabin und Miller macht die Sache also im Grunde nur unnötig kompliziert.  --[[Benutzer:Franz Scheerer aus Wiesbaden|Franz Scheerer aus Wiesbaden]] ([[Benutzer Diskussion:Franz Scheerer aus Wiesbaden|Diskussion]]) 12:10, 15. Jan. 2023 (CET)
: Das ist natürlich Unsinn, weil hier ein einzelner Apfel mit einer ganzen Apfelernte gleichgesetzt wird.
: Wahrscheinlichkeit ist nicht gleich Wahrscheinlichkeit genauso nicht Unendlich nicht gleich Unendlich ist.
: Es gibt eine zufällige eine niedrige, eine hohe und eine sehr hohe Wahrscheinlichkeit.
: und du verwechselst alles miteinander.
: Der Miller-Rabin-Test hat folgende Wahrscheinlichkeit, das n eine Primzahl ist
: (1/4)^ Je-Zeugenversuch
: 1 Versuch = (1/4) ^ 1 = 4 zu 1
: 2 Versuche = (1/4) ^2 = 16 zu 1
: 3 Versuche = (1/4) ^3 = 64 zu 1
: 5 Versuche = (1/4) ^4 = 256 zu 1
: 10 Versuche = (1/4) ^ 10 = 1.048.576 zu 1
: 100 Versuche = (1/4) ^ 100 = 1,606 * 10^ 60 zu 1
: 164 Versuche = (1/4 ^ 164 = 5,48 * 10 ^ 98 zu 1
: Mehr kann mein Taschenrechner nicht.
[[Spezial:Beiträge/170.133.12.82|170.133.12.82]] 15:30, 8. Aug. 2023 (CEST)

:Du sprichst hier von der theoretischen Möglichkeit, dass der Test versagt, dass eine vermeintliche Primzahl nach Rabin-Miller-Test tatsächlich doch zusammengesetzt ist. Das spielt in der Praxis keine Rolle, denn Zahlen mit mehreren hundert Stellen, die den Test bestehen, sind praktisch immer Primzahlen. Ich kenne keine Ausnahmen. In diesem Zusammenhang gibt es auch keinen Unterschied, zwischen Fermat-, Euler und Rabin-Miller-Test. 
:Ich verwende in der Praxis sogar immer nur den simplen Test von Fermat, obwohl mit Euler nur (p-1)/2 statt (p-1) im Exponenten steht. Dies bedeutet, wir sparen eine Quadrierung bei Square and Multiply. Eine von 1000, wenn wir eine Primzahl mit 1000 Bits suchen. Es spielt keine Rolle. Mit dem noch komplizierteren [[Rabin-Miller-Test]] könnten wir eventuell weitere Quadrierungen sparen, aber es ist nicht relevant. Wir können die Kosten für den Test auf andere Weise weit stärker reduzieren, durch eine Vorauswahl. Zum Beispiel, indem wir nur ungerade Zahlen (wir wissen gerade Zahlen größer zwei sind keine Primzahlen) testen. Wir können außerdem die Vielfachen kleiner Primzahlen so vorher, vor dem Fermat-Test, aussieben. Dies beschleunigt den Gesamttest erheblich. --[[Spezial:Beiträge/94.114.243.248|94.114.243.248]] 09:08, 10. Aug. 2023 (CEST)
::Genau, der Rabin-Miller-Test bringt gegenüber Fermat nur eine unbedeutende Beschleunigung. Entscheidend ist eine Vorselektion der Primzahlkandidaten. --[[Spezial:Beiträge/94.114.243.248|94.114.243.248]] 07:55, 12. Aug. 2023 (CEST)
::Wieso versteh ich nicht. Ich brauch' doch nur die Testzahl  durch SQR(10^9) zu teilen. (SQR = Wurzel). Schon hab ich alle Pseudoprimzahl-Möglichkeiten bis 1000.000.000 ausgeschlossen. Dazu brauch ich doch nicht den umständlichen Fermat-Test.
::Ein wesentlich einfacheres Voraus-Sieb als der Fremat-Test. Aber jeder wie er will. Ich halte der Miller-Rabin-Test für sicherer. Schließlich will ich der NSA keine Freude machen. [[Spezial:Beiträge/170.133.12.82|170.133.12.82]] 16:37, 9. Okt. 2023 (CEST)

== Frage zu Beispiel-Code ==

Ich arbeite nicht mit C++, ich vermuten aber, dass 
" u32 d  ...  while ((d /= 2) != 0) " die Nachkomma-Stellen abschneidet, was auf (bei ungeraden d) (d-1)/2 herausläuft. Ist das korrekt? Ich könnte das natürlich nachschlagen und wahrscheinlich ist diese Umsetzung auch eine sehr effiziente Lösung, aber ich finde, dass eine Erklärung für C++-Laien in den Kommentar des Codes gehört. Danke --[[Benutzer:Fredric|Fredric]] ([[Benutzer Diskussion:Fredric|Diskussion]]) 21:43, 30. Sep. 2024 (CEST)
:Richtig, wenn zwei Ganzzahlen dividiert werden, ist das Ergebnis auch ganzahlig, der Nachkommateil wird abgeschnitten.
:Man könnte es auch mit dem Rechtsschiebeoperator formulieren:
:while ((d >>= 1) != 0) { ... }
:Für in C Unerfahrene ist das aber wohl erst recht nicht unmittelbar verständlich.--[[Benutzer:Megatherium|Megatherium]] ([[Benutzer Diskussion:Megatherium|Diskussion]]) 22:34, 1. Okt. 2024 (CEST)
::Ich wollte gerade einen erklärenden Kommentar schreiben, aber ich verstehe noch etwas nicht: wenn in "while ((d /= 2) != 0) {  // potenziere modular: p = a^d mod n ... " das a hoch d kongruent 1 modulo n  berechnet werden soll, verstehen ich das mehrfache d/2 bis d==0 nicht, denn das entspräche doch  a hoch log d kongruent 1 modulo n , oder? --[[Benutzer:Fredric|Fredric]] ([[Benutzer Diskussion:Fredric|Diskussion]]) 21:23, 4. Okt. 2024 (CEST)
:::Hier wird a hoch d berechnet, und es wird dafür die [[Binäre Exponentiation]] verwendet. Dabei bestimmen die 1-Bits des Exponenten d, welche Potenzen der Basis a miteinander multipliziert werden müssen. Das Ergebnis wird außerdem modulo n berechnet, und dazu kann man alle Zwischenergebnisse bereits modulo n nehmen, wodurch diese (hier) kleiner als 2 hoch 64 bleiben. Und die Prüfung, ob a hoch d kongruent 1 ist, erfolgt erst danach.--[[Benutzer:Megatherium|Megatherium]] ([[Benutzer Diskussion:Megatherium|Diskussion]]) 13:36, 5. Okt. 2024 (CEST)
::::Danke erst mal für die schnelle und ausführliche Antwort und dass ich etwas dazu lernen konnte. Meine Unwissenheit soll hier kein Thema sein, aber das: Wie weit geht es denn mit dem Wiki-Gedanken, bzw. den Vorgaben überein, dass ein Code-Beispiel da ist, dass man nur mit erheblichen Grundwissen bzw. dem nicht vorhandenen Link auf Binäre Exponentiation verstehen kann? Wäre da nicht erst ein mal ein einfacher (ineffizienter) Code, der möglichst ähnlich zum Text von "Algorithmus" ist, besser? --[[Benutzer:Fredric|Fredric]] ([[Benutzer Diskussion:Fredric|Diskussion]]) 20:30, 5. Okt. 2024 (CEST)

== Bitte Erklärung des Sinns der Folge <math>(a^d, a^{2d}, a^{4d}, \ldots, a^{2^{j-1}d}, a^{2^jd})</math> ==

1. Zunächst wird erst mal einfach die Gleichung 
" <math>n - 1 = 2^j\cdot d</math> " festgelegt.

2. Dann wird (zwar korrekterweise aber ohne jeden Hinweis) klargestellt, dass dann auch eine Gleichung funktioniert, die auf beiden Seiten die gleiche (beliebige) Basis hat und die Teile der ersten Gleichung als Potenz verwendet wird. 

3. Dann muss man in " <math> a^{n-1} \equiv 1 \pmod n</math> " nur noch den kleinen fermatschen Satz wiedererkennen, womit dann auch " <math>a^{2^jd} \equiv 1 \pmod n</math> " gilt.

Der Anfang der Folge <math>(a^d, a^{2d}, a^{4d}, \ldots, a^{2^{j-1}d}, a^{2^jd})</math> , also <math>a^d</math> kommt im Abschnitt Algorithmus vor, aber der Zusammenhang wird nicht erklärt. --[[Benutzer:Fredric|Fredric]] ([[Benutzer Diskussion:Fredric|Diskussion]]) 15:51, 24. Okt. 2024 (CEST)

== Messungen zur Rundenanzahl ==

JPF 2025-10-06:

Eine Zählung  der Anzahl der Versuche, eine Zahl als zusammengesetzt zu erkennen - mit dem MRT-Algorithmus, so wie er auf der englischen Version dieser Seite beschrieben ist - ergab die folgende Liste für ungerade Zahlen von 1 bis 500_000_000:

[223643100, 991, 38, 4, 1, 0, 0, 0, 0, 0, 0, 26355866]

Das heißt: 223_643_100 Zahlen benötigten 1 Versuch (= ein einziger Basiswert), 991 Zahlen deren 2, ..., 1 Zahl deren 5, 0 Zahlen deren 6 .. 11, bis sie als zusammengesetzt erkannt wurden; und schließlich: 26_355_866 Zahlen überlebten 12 Versuche - diese wurden daher als Primzahlen betrachtet / erkannt.

Ein paar Beobachtungen:

# Die Anzahl der (ungeraden) Primzahlen unter 500 Mio. ist korrekt - siehe zB. [https://people.mpim-bonn.mpg.de/zagier/files-restricted/scanned/DieErsten50MillionenPrimzahlen.pdf https://people.mpim-bonn.mpg.de/zagier/files-restricted/scanned/DieErsten50MillionenPrimzahlen.pdf] Seite 10.
# Nicht-Primzahlen, die > 1 Versuche benötigen, sind selten.
# Die Anzahl der Versuche für eine Nicht-Primzahl kommt nie auch nur in die Nähe der 12; die 12 ist also recht hoch gewählt.
# Die Dichte der Zahlen, die > 1 Versuche benötigen, wird mit zunehmender Größe kleiner; hier die Anzahl der Zahlen, die > 2 Versuche benötigten, auf Bereiche heruntergebrochen: 0 - 100 Mio: 23; 100 - 200 Mio: 8; 200 - 300 Mio: 2; 300 - 400 Mio: 8; 400 - 500 Mio: 2. In den Bereichen, in denen Primzahltests "normalerweise" verwendet werden (2 ^ 1000 = 10 ^ 300 oder so, zB. für RSA), ist die Dichte noch sehr viel geringer. In der Tat habe ich noch keine einzige solche Zahl gesehen ...

Mir ist noch etwas eingefallen zum Punkt 3: Es ist ok, die Primzahl-Erkennung-Grenze (PEG, oben = 12) recht hoch zu wählen, denn: Ich benutze den MRT nur bei der _Suche_ nach einer Primzahl (hinter einem Zufalls-Startwert), und da wird der volle Wert der PEG nur bei der letzten Zahl verwendet, die damit als prim erkannt ist. Auf dem Weg dazwischen wird der MRT mit den zusammengesetzten Zahlen schnell fertig, wie oben beschrieben. {{unsigniert|~2025-27996-42|08:56, 7. Okt. 2025 (CEST)}}

--[[Spezial:Beiträge/&#126;2025-27845-71|&#126;2025-27845-71]] ([[Benutzer Diskussion:&#126;2025-27845-71|Diskussion]]) 13:07, 6. Okt. 2025 (CEST)