Fehlerwahrsch. Miller-Rabin < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:16 Mi 08.08.2007 | | Autor: | TheEraser |
Hallo Leute,
ich habe gerade die folgende Aussage Wikipedia entnommen:
Ist [mm] n\geq [/mm] 3 ungerade und nicht prim, so enthält die Menge [mm] \{1,2,\dots,n-1\} [/mm] höchstens [mm] \frac{n-1}{4} [/mm] Elemente a, ggT(a,n) = 1 die kein Zeuge für die Zusammengesetztheit von n sind.
Entnommen von: ![[]](/images/popup.gif) Miller-Rabin Test
Mir geht es aber wie im Betreff erwähnt darum:
1.) Wo is der Beweis der Aussage?
2.) Kann ich das auch auf den kleinen Satz des Fermat anwenden? Kleiner Fermat
Ich kann das nachvollziehen und habe es anhand des Beispiels n=15 auch geprüft (mit dem kleinen Satz des Fermat).
Für n=15 gibt es genau 4 Elemente die kein Zeuge für die Zusammengesetztheit von n sind (1,4,13,14)
und [mm]\bruch{15-1}{4}[/mm]=3,5 also rund 4
Aber ich bin mir nicht sicher ob man das einfach so benutzen kann, da ich ja auch keinen Beweis finde bzw. mir herleiten kann.
Viell. kann mir ja jmd. helfen ;)
Mfg
TE
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:06 Sa 11.08.2007 | | Autor: | mathpsycho |
Ich sehe keinen Bezug zur Wahrscheinlichkeitsrechnung. Die Frage gehört wohl eher in den Bereich Zahlentheorie. Außerdem gehört der Satz meines Wissens auch nicht zum Stoff der Oberstufe. Deshalb solltest Du besser in einem der Uni-Foren danach fragen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:50 So 12.08.2007 | | Autor: | Gilga |
Ich hatte das Thema im Hauptstudium Mathematik
Schau mal in dieses Skript http://www-m9.ma.tum.de/%7Etaraz/skript/zds.pdf
5.3. Erklärt probabilistische Primzahltests.
Ich finde das Skript recht gut!
Kann ich das auch auf den kleinen Satz des Fermat anwenden?
Du meinst ob höchstens (n-1)/4 Zahlen eine Zahl pseudoprim bei fermat erschienen lässt? ---Schau mal im Skript nach.....
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:20 So 12.08.2007 | | Autor: | felixf |
Hallo!
> Ich hatte das Thema im Hauptstudium Mathematik
> Schau mal in dieses Skript
> http://www-m9.ma.tum.de/%7Etaraz/skript/zds.pdf
> 5.3. Erklärt probabilistische Primzahltests.
>
> Ich finde das Skript recht gut!
>
> Kann ich das auch auf den kleinen Satz des Fermat
> anwenden?
> Du meinst ob höchstens (n-1)/4 Zahlen eine Zahl pseudoprim
> bei fermat erschienen lässt? ---Schau mal im Skript
> nach.....
Stichwort: Carmichael-Zahlen. Beim Fermat-Test kann man insb. bei denen ziemlich auf die Schnauze fallen.
Und schau auch mal hier. Ich find's ein wenig komisch, dass man vom Miller-Rabin-Test bei Wikipedia nicht an prominenter Stelle direkt einen Link dorthin findet, da der Test praktisch eine Weiterentwicklung vom Fermat-Test ist.
LG Felix
|
|
|
| |
|
Halo,
erstmal danke für eure Antworten.
Ich hab mein Problem sicher nicht vollständig formuliert.
Hier nochmal das Zitat:
Ist $ [mm] n\geq [/mm] $ 3 ungerade und nicht prim, so enthält die Menge $ [mm] \{1,2,\dots,n-1\} [/mm] $ höchstens $ [mm] \frac{n-1}{4} [/mm] $ Elemente a, ggT(a,n) = 1 die kein Zeuge für die Zusammengesetztheit von n sind.
^^Das heisst, dass die Fehlerwahrscheinlichkeit des Miller-Rabin Test´s bei nicht einmal $ [mm] \bruch{1}{4} [/mm] $ liegt.
Mir fehlt nur für dieses Zitat eine Begründung...
Und meine 2. Frage ist, wie man dieses Zitat auf den kleinen Fermat anwenden kann.
Ich hoffe Ihr wisst nun wie ichs meine. ;)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:06 Mo 13.08.2007 | | Autor: | felixf |
Hallo
> erstmal danke für eure Antworten.
>
> Ich hab mein Problem sicher nicht vollständig formuliert.
>
> Hier nochmal das Zitat:
>
> Ist [mm]n\geq[/mm] 3 ungerade und nicht prim, so enthält die Menge
> [mm]\{1,2,\dots,n-1\}[/mm] höchstens [mm]\frac{n-1}{4}[/mm] Elemente a,
> ggT(a,n) = 1 die kein Zeuge für die Zusammengesetztheit von
> n sind.
>
> ^^Das heisst, dass die Fehlerwahrscheinlichkeit des
> Miller-Rabin Test´s bei nicht einmal [mm]\bruch{1}{4}[/mm] liegt.
>
> Mir fehlt nur für dieses Zitat eine Begründung...
Hab mal kurz nach ``miller rabin test'' gegoogelt und dabei folgendes Dokument gefunden: http://www.rzuser.uni-heidelberg.de/~mfelis/proseminar-krypt.pdf
Es enthaelt u.a. einen Beweis fuer diese Aussage (Satz 4.3 auf Seite 4).
> Und meine 2. Frage ist, wie man dieses Zitat auf den
> kleinen Fermat anwenden kann.
Du musst dich hier schon etwas genauer ausdruecken. Eine aehnliche Aussage mit ``...gibt es hoechstens...'' (mit einer Zahl, die in etwa ein Vielfaches von $n$ ist) gibt es nicht, da es Carmichael-Zahlen gibt, bei denen jede zu der Zahl teilerfremde Zahl kein Zeuge ist.
LG Felix
|
|
|
| |
|
Danke für die Antwort.
Stimmt. Die Carmichael-Zahlen machen einem da einen Strich durch die Rechnung.
Aber beim Miller Rabin Test tauchen ja auch starke Pseudoprimzahlen auf.
Gibt es denn dann einen Weg um die Fehlerwahrscheinlichkeit für den Miller Rabin Test herauszubekommen?
Bzw. wenigstens eine Abschätzung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Sa 15.09.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
