www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieMiller-Rabin-Algorithmus
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Zahlentheorie" - Miller-Rabin-Algorithmus
Miller-Rabin-Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Miller-Rabin-Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:02 Fr 05.04.2013
Autor: el_grecco

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


        
Bezug
Miller-Rabin-Algorithmus: Gedanke
Status: (Antwort) fertig Status 
Datum: 11:48 Fr 05.04.2013
Autor: wieschoo


> Wurde einmal "nicht prim" geantwortet: RETURN "nicht prim" 

[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]?

Bezug
                
Bezug
Miller-Rabin-Algorithmus: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
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  []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


Bezug
                        
Bezug
Miller-Rabin-Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 01:18 Sa 06.04.2013
Autor: 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 [/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

Bezug
                                
Bezug
Miller-Rabin-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                        
Bezug
Miller-Rabin-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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)

Bezug
                                
Bezug
Miller-Rabin-Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:54 So 07.04.2013
Autor: el_grecco

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


Bezug
                                        
Bezug
Miller-Rabin-Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 19:17 Mi 10.04.2013
Autor: wieschoo

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

Bezug
                
Bezug
Miller-Rabin-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                        
Bezug
Miller-Rabin-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                
Bezug
Miller-Rabin-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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




Bezug
                                        
Bezug
Miller-Rabin-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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].
Ich war nur etwas verwirrt.

LG
wieschoo

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]