Miller-Rabin-Test: ggT(a,n)=1 wichtig? |
| 07.08.2010, 12:52 | KlausDieter | Auf diesen Beitrag antworten » | ||||
| Miller-Rabin-Test: ggT(a,n)=1 wichtig? ich habe eine Frage zum Miller-Rabin-Test. Und zwar sieht man in vielen Beschreibungen, dass wenn man überprüfen möchte ob n eine Primzahl ist, man ein zu n teilfremdes a wählt (also ggT(a,n) =1) und den entsprechenden Test durchführt. Mir ist natürlich klar, dass falls ggT(a,n) > 1 ist, man sofort schließen kann, dass n keine Primzahl ist. Aber ist dieser ggT(a,n)=1 Test wirklich wichtig? Sprich, würde ich diesen streichen und direkt den eigentlichen Miller-Rabin-Test durchführen, würde die Fehlerwahrscheinlichkeit bei größer als 1/4 liegen? Bzw. anders gesagt: Wenn ich ein a wähle mit ggT(a,n) > 1, würde dieses dann öfter ein Zeuge für die nicht zusammengesetztheit von n sein? Wäre dankbar wenn mir da jemand weiterhelfen könnte. |
||||||
| 07.08.2010, 13:54 | wisili | Auf diesen Beitrag antworten » | ||||
RE: Miller-Rabin-Test: ggT(a,n)=1 wichtig?
... ist schon mal falsch. |
||||||
| 07.08.2010, 14:23 | kiste | Auf diesen Beitrag antworten » | ||||
gilt beim Miller-Rabin-Test, also passt das schon. |
||||||
| 08.08.2010, 13:19 | Mystic | Auf diesen Beitrag antworten » | ||||
RE: Miller-Rabin-Test: ggT(a,n)=1 wichtig?
wisili und kiste haben natürlich beide recht: Dass du in diesem Zusammenhang die wesentliche Voraussetzung 0<a<n mit keinem Wort erwähnst, die man für diesen Schluss unbedingt braucht, würde mir jetzt auch nicht gefallen, andererseits ist diese Voraussetzung üblicherweise Teil des Miller-Rabin-Tests...
Ob dieses die Überprüfung der Bedingung ggT(a,n)=1 mit in den Test aufnimmst oder nicht, das beieinflußt das Ergebnis in keinster Weise: Wenn ggT(a,n)>1 für ein a mit 0<a<n gilt, so ist dann auch der eigentliche Miller-Rabin-Test nicht erfüllt... Immerhin müsste, ja im Verlaufe des Tests für eine gewisses k>0 gelten, was für ggT(a,n)>1 natürlich nicht sein kann... Die eigentlich interessante Frage ist daher: SOLL man die Überprüfung ggT(a,n)=1 aus algorithmischer Sicht überhaupt durchführen?... Genaugenommen läßt sich diese Frage gar nicht allgemein beantworten ohne die Vorgeschichte des Tests zu kennen... Weiß man jedoch aufgrund von Vortests, dass n sicher keine "kleinen" Primfaktoren besitzt, so wäre die Überprüfung dieser Bedingung dann mit an Sicherheit grenzender Wahrscheinlichkeit reine Zeitverschwendung... |
||||||
| 09.08.2010, 14:22 | KlausDieter | Auf diesen Beitrag antworten » | ||||
Hallo Mystic, ah okay, das ist natürlich interessant. Nur ist mir leider noch nicht ganz klar, warum nicht gelten kann, wenn ggT(a,n) > 1 gilt. |
||||||
| 09.08.2010, 14:24 | KlausDieter | Auf diesen Beitrag antworten » | ||||
Ach ne ist schon klar, man kann über die Einheitengruppe argumentieren. Wäre a^k = 1 mod n, wäre a^(k-1) das Inverse zu a. Das ist aber ein Widerspruch, denn für Einheiten muss ggT(a,n)=1 gelten. |
||||||
| Anzeige | ||||||
|
|
||||||
| 09.08.2010, 19:45 | Mystic | Auf diesen Beitrag antworten » | ||||
Das stimmt zwar, ist aber unnötig kompliziert...Viel elementarer geht es so: |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
Wichtig: