Miller-Rabin-Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Satz:
Sein [mm] $n\!\$ [/mm] Carmichael-Zahl. Der Anteil [mm] $x1$ [/mm] beträgt mindestens 75%.
Satz (Miller-Rabin-Algorithmus):
Eingabe [mm] $n\!\$
[/mm]
Wiederhole Folgendes [mm] $a\!\$-mal:
[/mm]
Wähle [mm] $x
Bestimme [mm] $x^{n-1} \text{ mod } [/mm] n=:u$
Falls $u > [mm] 1\!\$ [/mm] antworte: "Nicht prim"
Falls [mm] $u=1\!\$:
[/mm]
Prüfe ob ein $i [mm] \leq \log [/mm] n$ existiert mit:
[mm] $ggT(x^{\bruch{(n-1)}{2^i}}-1,n)>1$
[/mm]
Falla ja, antworte: "Nicht prim" (dieser ggT ist Teiler von [mm] $n\!\$)
[/mm]
Wurde einmal "nicht prim" geantwortet: RETURN "nicht prim"
Ansonsten: RETURN "prim"
Satz:
Liefert der Miller-Rabin-Test die Antwort "nicht prim", so ist die Eingabe zusammengesetzt.
Liefert der Miller-Rabin-Test die Antwort "prim", so ist die Wahrscheinlichkeit, dass [mm] $n\!\$ [/mm] zusammengesetzt ist [mm] $\leq (\bruch{1}{2})^a$. [/mm] |
Hallo,
ich kämpfe mich gerade durch die Vorbereitung für die Klausur des letzten Leistungsnachweises des Bachelorstudiums (Vorlesung Komplexitätstheorie). Das Obere ist keine Aufgabe, sondern aus dem Skript abgeschrieben. Kann mir bitte jemand erklären, was es mit den beiden folgenden Zeilen auf sich hat:
Prüfe ob ein $ i [mm] \leq \log [/mm] n $ existiert mit:
$ [mm] ggT(x^{\bruch{(n-1)}{2^i}}-1,n)>1 [/mm] $
Warum bildet man den Logarithmus und wie kommt man auf den Bruch im Exponenten (falls dafür ein langer Beweis nötig sein sollte, bitte nicht die Mühe machen, ihn niederzuschreiben, denn ein kurzer Kommentar oder ein Link genügen)?
Vielen Dank!
Gruß
el_grecco
|
|
| |
|
> Wurde einmal "nicht prim" geantwortet: RETURN "nicht prim"
![[ok]](/images/smileys/ok.gif "[ok]")
> Ansonsten: RETURN "prim"
Eher: "RETURN vermutlich prim"
Ist [mm]n[/mm] eine ungerade Primzahl, so ist [mm]n-1[/mm] gerade und lässt sich schreiben als [mm]n-1=2^i\cdot d[/mm] mit [mm]d[/mm] ungerade. Wie groß kann [mm]i[/mm] maximal sein?
Nach Fermat ist entweder [mm]a^{d}\equiv 1\pmod{n}[/mm] oder [mm]a^{2^r\cdot d}\equiv -1\pmod{n}[/mm] für ein [mm]0\le r \le i-1[/mm] .
Miller Rabin baut eine Kontraposition daraus:
Man sucht ein [mm]a[/mm] mit [mm]a^r\not\equiv 1\pmod{n}[/mm] und [mm]a^{2^r\cdot d}\not\equiv -1\pmod{n}[/mm] für alle [mm] $0\le r\le [/mm] i-1$.
Was ist [mm]2^i[/mm] mit [mm]i=\log_2 n[/mm]?
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 23:13 Fr 05.04.2013 | | Autor: | el_grecco |
Hallo wieschoo,
> Ist [mm]n[/mm] eine ungerade Primzahl, so ist [mm]n-1[/mm] gerade und lässt
> sich schreiben als [mm]n-1=2^i\cdot d[/mm] mit [mm]d[/mm] ungerade. Wie groß
> kann [mm]i[/mm] maximal sein?
>
das mit n-1 ist mir klar. Wie kommst du aber auf diese Gleichung bzw. gibt es dafür eine Bezeichnung?
Ich denke das maximale [mm] $i\!\$ [/mm] ist [mm] $\log_2 \bruch{n-1}{d}$.
[/mm]
> Nach Fermat ist entweder [mm]a^{d}\equiv 1\pmod{n}[/mm] oder
> [mm]a^{2^r\cdot d}\equiv -1\pmod{n}[/mm] für ein [mm]0\le r \le i-1[/mm] .
>
Da kann ich leider auch nicht folgen. Also ich sehe mir den ![[]](/images/popup.gif) kleinen fermatschen Satz an, aber ich erkenne den Zusammenhang nicht.
> Miller Rabin baut eine Kontraposition daraus:
> Man sucht ein [mm]a[/mm] mit [mm]a^r\not\equiv 1\pmod{n}[/mm] und
> [mm]a^{2^r\cdot d}\not\equiv -1\pmod{n}[/mm] für alle [mm]0\le r\le i-1[/mm].
>
> Was ist [mm]2^i[/mm] mit [mm]i=\log_2 n[/mm]?
Eventuell sehe ich es, wenn meine obigen Probleme geklärt sind.
Ich danke Dir!
Gruß
el_grecco
|
|
|
| |
|
Meinst du die Kongruenzen? Für p ungerade und prim gilt erst einmal für 1<a<p die Teilerfremdheit von a und p.Ergo
[mm] $a^{p-1}\equiv 1\pmod [/mm] p$
Mit den gleichen Notationen wie in der vorherigen Antwort ist doch:
[mm] $a^{p-1}=a^{2^rd}=(a^{2^{r-1}d})^2\equiv 1\pmod [/mm] p$
Das sind Rechnungen in einem Körper also gibt von [mm] $x^2-1$ [/mm] maximal zwei Lösungen. Also [mm] $a^{2^{r-1}d}\equiv \pm [/mm] 1 [mm] \pmod [/mm] p$
Die andere Kongruenz ist wirklich leicht, denn [mm] $p\mid a^{p-1}-1$
[/mm]
gruß
wieschoo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:10 Sa 06.04.2013 | | Autor: | el_grecco |
Hallo wieschoo,
ich habe mir deine beiden Beiträge sauber auf Papier geschrieben und angesehen, habe aber Schwierigkeiten zu folgen. Meine Probleme sind speziell die Fragen aus meinem letzten Beitrag. Wäre nett, wenn du etwas besser darauf eingehen könntest (sorry für die Umstände, aber ich sehe gerade kein Licht am Ende des Tunnels).
Danke!
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:55 Sa 06.04.2013 | | Autor: | wieschoo |
> Hallo wieschoo,
Ich kann mich da auch nur ausführlich wiederholen.
>
> > Ist [mm]n[/mm] eine ungerade Primzahl, so ist [mm]n-1[/mm] gerade und lässt
> > sich schreiben als [mm]n-1=2^i\cdot d[/mm] mit [mm]d[/mm] ungerade. Wie
> groß
> > kann [mm]i[/mm] maximal sein?
> >
>
> das mit n-1 ist mir klar. Wie kommst du aber auf diese
> Gleichung bzw. gibt es dafür eine Bezeichnung?
Das ist einfach nur ein Ansatz und die Idee. Man zerlegt einfach n-1. Eben wegen [mm]a^{\blue{n-1}}\equiv 1 \pmod n[/mm] und n ungerade prim.
>
> Da kann ich leider auch nicht folgen. Also ich sehe mir den
> kleinen fermatschen Satz
> an, aber ich erkenne den Zusammenhang nicht.
Idee: Die Eingabe ist eine Zahl [mm]n\in\IZ[/mm]. Angenommen diese Zahl [mm]n[/mm] ist eine ungerade Primzahl. Dann ist [mm]n-1[/mm] eine gerade Zahl und lässt sich zerlegen in [mm]n-1=2^r\cdot d[/mm] mit [mm]r,d\in \IN[/mm].
Nach Fermat ist also [mm] a^{p-1}=a^{2^rd}=(a^{2^{r-1}d})^2\equiv 1\pmod p [/mm]. Da alles in einem Körper [mm]\IZ/n\IZ[/mm] stattfindet ([mm]n[/mm] war prim) und [mm]x^2=1[/mm] nur die Lösungen [mm]+1,-1[/mm] in dem Körper haben kann, muss zwangsläufig [mm]\blue{a^{2^{r-1}d}} \equiv \pm 1 \pmod p[/mm] gelten.
Wäre [mm]n[/mm] zusammengesetzt, so gäbe es hier mehrere Lösungen nach dem chinesischen Restsatz. (Es gibt zum Beispiel für [mm]n=4[/mm] mehrere Wurzeln der 1, etwa 1,3,7, ..)
Satz: Aus [mm]a\in\IZ,p\in \mathbb{P}[/mm] mit [mm]p[/mm] ungerade und [mm]p-1=2^r\cdot d[/mm] folgt stets [mm]a^d\equiv 1 \pmod p[/mm] oder es gibt ein [mm]r[/mm] mit [mm]a^{2^rd}\equiv -1 \pmod p[/mm].
Rabin-Miller nimmt nutz das indirekt aus.
Schau mal unter
http://www.math.utah.edu/~savin/book08_jun.pdf
Seite 137 (mit Beispiel)
|
|
|
| |
|
Hallo wieschoo,
> Meinst du die Kongruenzen? Für p ungerade und prim gilt
> erst einmal für 1<a<p die Teilerfremdheit von a und
> p.Ergo
>
> [mm]a^{p-1}\equiv 1\pmod p[/mm]
> Mit den gleichen Notationen wie in
> der vorherigen Antwort ist doch:
> [mm]a^{p-1}=a^{2^rd}=(a^{2^{r-1}d})^2\equiv 1\pmod p[/mm]
>
> Das sind Rechnungen in einem Körper also gibt von [mm]x^2-1[/mm]
> maximal zwei Lösungen. Also [mm]a^{2^{r-1}d}\equiv \pm 1 \pmod p[/mm]
>
> Die andere Kongruenz ist wirklich leicht, denn [mm]p\mid a^{p-1}-1[/mm]
>
gut möglich, dass es inzwischen total trivial ist, aber mir erschließt sich noch nicht der Teil des Algorithmus "Prüfe ob ein $i [mm] \leq \log [/mm] n $ existiert mit: $ [mm] ggT(x^{\bruch{(n-1)}{2^i}}-1,n)>1$." [/mm] Wäre cool, wenn Du mir helfen kannst.
Übrigens Danke für Deine Mitteilung, jetzt sind mir die Schritte klar und die entsprechende Frage kann auf "beantwortet" markiert werden! 
> gruß
> wieschoo
Gruß
el_grecco
|
|
|
| |
|
Dein [mm]\frac{n-1}{2^i}[/mm] entspricht doch dem laufenden [mm]k[/mm] von Seite 137. Es gilt doch [mm]\lfloor\log_2(n)\rfloor[/mm] ist die Anzahl der 2er Potenzen.
Statt das [mm]k[/mm] von Seite 137 hoch laufen zu lassen, testest du die gleichen Zahlen nur in umgedrehter Reihenfolge.
Wobei ich jetzt Glaube (???), dass es eher
[mm]ggT(x^{\bruch{(n-1)}{2^i}}\blue{+}1,n)>1 \iff n \mid x^{\bruch{(n-1)}{2^i}}\blue{+}1 \iff x^{\bruch{(n-1)}{2^i}}\equiv -1 \pmod n[/mm]
sein sollte.
Zeig doch mal, was du gerechnet hast. Oder stell doch mal um [mm]n-1=2^kq\implies q=\frac{n-1}{2^k}[/mm].
Gruß
wieschoo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:44 Fr 05.04.2013 | | Autor: | felixf |
Moin!
> Nach Fermat ist entweder [mm]a^{d}\equiv 1\pmod{n}[/mm] oder
> [mm]a^{2^r\cdot d}\equiv -1\pmod{n}[/mm] für ein [mm]0\le r \le i-1[/mm] .
Nein, nicht ganz. So ein $i$ gibt es nur dann, wenn die multiplikative Ordnung von $a$ in [mm] $(\IZ/n\IZ)^\ast$ [/mm] ein Teiler von $n - 1$ ist. Das muss sie aber nicht sein, da $n$ nicht prim ist. Deswegen hilft der Satz von Fermat hier auch nicht weiter.
Aber wenn die Ordnung von $a$ kein Teiler von $n - 1$ ist, dann weiss man eh, dass $n$ nicht prim sein kann. (Das folgt aus dem Satz von Fermat.) Und das ist eben auch ein Teil vom Miller-Rabin-Test (und zwar der Fermat-Test.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:57 Sa 06.04.2013 | | Autor: | wieschoo |
Ich seh leider nicht worauf du hinaus möchtest und sehe den Fehler nicht. Ich begann doch den Beitrag mit "n ungerade Primzahl". Für beliebige ungerade Zahlen stimmt dies natürlich nicht. (starke a Pseudoprimzahlen)
gruß
wieschoo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:39 So 07.04.2013 | | Autor: | felixf |
Moin wieschoo
> Ich seh leider nicht worauf du hinaus möchtest und sehe
> den Fehler nicht. Ich begann doch den Beitrag mit "n
> ungerade Primzahl". Für beliebige ungerade Zahlen stimmt
> dies natürlich nicht. (starke a Pseudoprimzahlen)
Du hast recht, ich hatte mich verlesen... Sorry :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:06 Mi 10.04.2013 | | Autor: | wieschoo |
> Moin wieschoo
>
> > Ich seh leider nicht worauf du hinaus möchtest und sehe
> > den Fehler nicht. Ich begann doch den Beitrag mit "n
> > ungerade Primzahl". Für beliebige ungerade Zahlen stimmt
> > dies natürlich nicht. (starke a Pseudoprimzahlen)
>
> Du hast recht, ich hatte mich verlesen... Sorry :)
>
> LG Felix
Macht ja nichts. Schau dir mal die Uhrzeit von dem betreffenden Beitrag an ![[koffein]](/images/smileys/koffein.gif "[koffein]") .
Ich war nur etwas verwirrt.
LG
wieschoo
|
|
|
|
