| |
| Autor |
  Solovay-Strassen-Test |
|
rijndael
Junior 
Dabei seit: 19.12.2007
Mitteilungen: 19
 |  Themenstart: 2007-12-25
|
Hallo zusammen,
ich schreibe eine Arbeit über Primzahlentestverfahren und beschäftige mich gerade mit dem Solovay-Strassen Test.
Dort wird das Kriterium
a^(p-1)/2=(a/b) mod p
für p=Primzahl angewendet, wobei a aus \IZ_n
ist und
(a/b)
das Jacobi-Symbol ist.
Nach dem Satz von Euler ist
a^(p-1)/2=+-1
Ich verstehe den Zusammenhang mit den quadratischen Resten nicht. Ich bereche das Jacobi-Symbol für eine Primzahl und wähle a so, dass es kein quadratischer Rest ist. Z.B. sei p=11 und a = 6. Das Ergebnis des Jakobi-Symbol ist -1 weil 6 kein quadr. Rest mod 11 ist. Jetzt rechne ich
6^5 mod 11 = 10
Also stimmt die Kongruenz nicht und 11 ist keine Primzahl.
Wo ist der Fehler in meiner Rechnung? Euler hat gezeigt das bei p=prim
a^(p-1)/2 = cases(1,a ist quadratischer Rest mod p;-1,a ist quadratischer Nichtrest mod p)
Sowohl 1 als auch -1 kann also das Ergebnis sein, insofern p primzahl ust.
Das nehme ich hin und glaube es. Was ich aber nicht verstehe ist, wie die Aussage über quadratische Reste in Zusammenhang mit der Eigenschaft als Primzahl steht.
Noch ein Nachtrag zum Satz von Euler: Ich habe geschrieben ich glaube das der Satz stimmt, aber ich verstehe es nicht. a=2, p=11. Laut Euler müsste
2^5 mod 11 = -1 sein,
es ist aber 10? Ich habe auch schon gelesen, dass
-1<=>10 mod 11
mir wäre schon geholfen, wenn mir das jemand erklären könnte.
danke
rijn
[ Nachricht wurde editiert von rijndael am 25.12.2007 18:25:23 ]
|
 Profil
|
Hyp
Senior 
Dabei seit: 08.03.2003
Mitteilungen: 1858
|  Beitrag No.1, eingetragen 2007-12-26
|
Hi,
wenn dir nicht klar ist, dass -1==10 (mod 11) ist, dann macht es wenig Sinn sich mit dem Euler-Kriterium oder dem Solovay-Strassen-Test zu beschäftigen.
Im Übrigen lautet das Euler-Kriterium wie folgt:
Für eine Primzahl p und ein a\el\IN mit p\teiltnicht\ a gilt
a ist quadratischer Rest modulo p genau dann, wenn a^((p-1)/2)==1 (mod p) ist.
Gruß,
Hyp
|
Profil
|
Fragezeichen
Senior
Dabei seit: 08.03.2004
Mitteilungen: 2954
Wohnort: München
 | Beitrag No.2, eingetragen 2007-12-26
|
Profil
|
fru
Senior 
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
 | Beitrag No.3, eingetragen 2007-12-26
|
\quoteon(2007-12-25 14:26 - rijndael)
Laut Euler müsste
2^5 mod 11 = -1 sein,
es ist aber 10? Ich habe auch schon gelesen, dass
-1<=>10 mod 11
mir wäre schon geholfen, wenn mir das jemand erklären könnte.
\quoteoff
\
Hallo Rijn, das kann ich Dir leicht erklären.
Statt des Äquivalenzpfeiles sollte ein Kongruenzzeichen stehen:
-1==10 mod 11
Um einzusehen, daß es sich dabei um eine wahre Aussage handelt, brauchst Du nur die Definition
a==b mod m
:<=>
m\|(a-b)
anzuwenden: -1 ist modulo 11 mit 10 kongruent, weil der Modul 11 ein Teiler der Differenz -1-10=-11 der beiden Seiten der Kongruenz ist.
Wenn man diese Definition nicht kennt \(oder auch: sie nur nicht anwenden kann), scheint es mir allerdings \- so wie Hyp \- sehr fraglich, ob man sich dann mit so weit über das Elementare Hinausgehendem überhaupt sinnvoll beschäftigen kann. Ich würde Dir daher dringendst empfehlen, die weitere Bearbeitung vorläufig zurückzustellen, um Dir vorher wenigstens die ersten Grundlagen der Teilbarkeitslehre anzueignen. Eine solche Investition wird sich mit Sicherheit bezahlt machen, während Du andernfalls Gefahr läufst, eine ziemlich fehlerhafte Arbeit abzuliefern.
Liebe Grüße, Franz
|
Profil
|
rijndael
Junior
Dabei seit: 19.12.2007
Mitteilungen: 19
|  Beitrag No.4, vom Themenstarter, eingetragen 2007-12-26
|
vielen dank @fru.
Das war der hinweis den ich gebraucht habe. natürlich hast du recht mit dem was du das anwenden der grundprinzipien sagst. Der Zusammenhang war mir wohl bewusst, aber für den Zusammenhang brauchte ich wohl diesen kleinen Denkantstoss.
rijn
|
Profil
|
rijndael hat die Antworten auf ihre/seine Frage gesehen.
rijndael hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
