Diskussion:Miller-Rabin-Test

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? --84.56.98.147 00:47, 28. Jan. 2008 (CET)

In der Literatur findet man den Algorithmus sowohl mit $n-1$ als Basis, als auch ohne. Deshalb habe ich den Hinweis entfernt. Ein Beispiel für den Algorithmus mit $n-1$ findet sich in Buchmanns „Einführung in die Kryptographie“ und ein Beispiel ohne $n-1$ im Buch „Prime Numbers“ von Crandall und Pomerance. --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. --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? --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^sd 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. --Arbol01 13:53, 30. Jun 2006 (CEST)

Die Prüfung auf Teilerfremdheit ist nicht notwendig. Wenn $a$ und $n$ nicht teilerfremd sind, dann ist

$a^{x}\not \equiv \pm 1\mod n$

und $a$ wird deshalb als zusammengesetzte Zahl erkannt. --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! --81.173.232.96 12:33, 4. Jul. 2007 (CEST)

Online Berechnung Miller-Rabin-Test

Hier gibt es einen online test. vielleicht wollt ihr ja einen weblink setzten. -- 81.173.252.78 00:28, 9. Okt 2006 (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. -- 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. --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 ${\frac {1}{2}}$ pro Schritt ist, ist meiner Meinung nach falsch. Im Beweis soll gezeigt werden, dass ein zusammengesetztes $n$ höchstens ${\frac {n-1}{2}}$ Entlastungszeugen hat. Dabei geht der Autor davon aus, dass $\mathbb {Z} _{n}^{*}$ eine Gruppe ist, was aber genau für zusammengesetzte $n$ falsch ist. --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 $n-1$, sondern $\phi (n)$, und damit ist der Schluss, dass es mindestens ${\frac {n-1}{2}}$ Belastungszeugen gibt, falsch.--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 $\mathbb {Z} _{n}^{*}:=\{a\in \mathbb {Z} _{n}:ggT(a,n)=1\}$. 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. --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. --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. --84.44.131.176 01:42, 23. Nov. 2006 (CET)

Quelltext Miller-Rabin-Test für sehr große Primzahlen

Unter: http://www.bcabrera.de/wordpress/?p=6#more-6 gibt es einen C++ beispielcode, mit dem beliebig große Zahlen mit dem Miller-Rabin- Test getestet werden können.Der Link wurde aber aus dem wiki gelöscht. Warum?

Zudem ist der verlinkte Quelltext für kleinere Zahlen veraltet.

Vielleicht weil er Passwortgeschützt ist und deswegen unbrauchbar ? 37.5.134.66 23:05, 4. Aug. 2013 (CEST)

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. -- 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. 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 . 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. 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. --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. --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. (nicht signierter Beitrag von 137.226.57.88 (Diskussion | Beiträge) 11:46, 5. Mär. 2010 (CET))

2 auch oder?

"wenn n < 9.080.191, ist es ausreichend a = 31 und 73 zu testen." (nicht signierter Beitrag von Tompazi (Diskussion | Beiträge) 19:01, 13. Mär. 2010 (CET))

Nein. Geht ohne 2. --Daniel5Ko 00:08, 6. Jan. 2012 (CET)

$n-1=d\cdot 2^{j}$ -> was ist J ?

Woher nehme ich die Zahl J ? Außerdem, einen Algorithmus kann man aus dieser unvollständigen Beschreibung partout nicht ableiten. 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. --Daniel5Ko (Diskussion) 23:37, 4. Aug. 2013 (CEST)

Vielen Dank erst mal. Gibt es auch einen programmierbaren Algorithmus ?. MfG. Dank im Voraus. 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.)

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

Eine Formulierung des Algorithmus für eine Basis a gibt es z.B. hier: [1]. 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. -- HilberTraum (Diskussion) 13:55, 9. Aug. 2013 (CEST)

Tausend Dank 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

$a^{d\cdot 2^{r}}\equiv -1\mod n$

für ein r mit 0 ≤ 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. --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. (nicht signierter Beitrag von 93.135.190.207 (Diskussion) 02:05, 21. Mai 2015 (CEST))

$a^{p-1}$ 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 $a^{d\cdot 2^{j}}$, also dann $a^{p-1}$ 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 $a^{2^{j-1}d}$. Dann kann n nicht prim sein, denn mit n prim muss als letztes Element 1 kommen und davor 1 oder n-1. --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². Die Menge {2, … , n − 2 } besteht aus genau n - 3 Elementen, und von diesen sind genau die Zahlen p, 2p, …, 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^x ≡ k g ( mod n )"? Gandalf Mithrandir 18:25, 10. Jun. 2018 (CEST)

Hm, der Satz geht ja noch weiter: „…, die keine Zeugen für die Zusammengesetztheit von $n$ sind.“ -- HilberTraum (d, m) 19:00, 10. Jun. 2018 (CEST)

Es gibt noch ein Fehler : statt 1/4^8 muss es heißen 1/4^s 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. --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. --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. --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. --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.

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. --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. --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. 170.133.12.82 16:37, 9. Okt. 2023 (CEST)