Modulare Potenzierung < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Leute,
es geht um den Miller-Rabin Primzahltest.
Dieser besitzt ja, wenn man die verallgemeinerte Riemansche Vermutung ausser Betracht lässt, eine Laufzeit von [mm] O(log(n)^3).
[/mm]
Ich habe gelesen, dass das so ist, da Modulare Potenzierung eine Laufzeit von [mm] O(log(n)^3) [/mm] hat.
Aber wie ist das zu erklären bzw. zu zeigen/beweisen?
Ich hoffe Ihr könnt mir helfen.
Bin am verzweifeln...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:06 Do 22.11.2007 | | Autor: | rainerS |
Hallo!
> es geht um den Miller-Rabin Primzahltest.
> Dieser besitzt ja, wenn man die verallgemeinerte
> Riemansche Vermutung ausser Betracht lässt, eine Laufzeit
> von [mm]O(log(n)^3).[/mm]
Für einen Test; das muss noch mit der Anzahl der Versuche malgenommen werden.
> Ich habe gelesen, dass das so ist, da Modulare Potenzierung
> eine Laufzeit von [mm]O(log(n)^3)[/mm] hat.
Das stimmt nicht. Der ![[]](/images/popup.gif) Square-and-Multiply -Algorithmus hat eine asymptotische Laufzeit von [mm]O(log(n))[/mm], wenn n der Exponent ist.
Der Miller-Rabin-Test muss in jedem Durchlauf eine Reihe von modularen Exponentiationen durchführen, dadurch kommt man auf [mm]O(k*log(n)^3)[/mm] bei k Durchläufen.
Viele Grüße
Rainer
|
|
|
|
