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.

Wahl der Basis

Wieso spielt es eine Rolle, dass die Zahl a gerade ist?

(nicht signierter Beitrag von 84.153.100.61 (Diskussion) 20:49, 21. Mai 2006)

Die Zahl a muss nicht ungerade sein! Ich denke hier liegt eine Verwechslung vor, denn dies ist lediglich bei n der Fall.

Siehe folgende Seiten zur Recherche: http://www-math.uni-paderborn.de/~k-heinz/de/body.primzahltest.html http://johannes-bauer.com/thi/millerrabin.php

(nicht signierter Beitrag von 84.153.120.220 (Diskussion) 20:49, 22. Mai 2006) (bearbeiten)

Ich habe den Fehler ausgebessert. --Squizzz 20:18, 26. Jun 2006 (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)

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)