| |
| Autor |
  Beweis zum Miller-Rabin-Test unverständlich |
|
stefanstiege
Wenig Aktiv 
Dabei seit: 26.10.2020
Mitteilungen: 32
 |  Themenstart: 2022-11-29
|
Hallo zusammen,
ich versuche gerade einen Beweis zum Miller-Rabin-Test (von \(n\in \mathbb{N}\)) nachzuvollziehen (aus Kryptologie von Karpfinger und Kiechle). Dort heißt es auf Seite 150, dass es mindestens ein Element \(a \in A (= \{a \in \{1,\dots,n-1\} \ | \ n \text{ ist starke Pseudoprimzahl zur Basis } a \})\) gibt, das die Kongruenz (modulo n) \(a^{2^rd} \equiv -1\) (*) erfüllt, da die starken Pseudoprimzahlen entweder direkt diese Eigenschaft erfüllen oder es \(a^d \equiv 1\) gilt. Dann schreiben sie, dass dann aber auch \((-a)^d \equiv -1\) gilt, was soweit verständlich ist, da \(d\) ungerade ist. Aber welches Element aus \(A\) existiert dann mit der Eigenschaft (*)? Das verwirrt mich etwas, da \(-a\) ja nicht ohne weiteres in der Menge \(A\) oben liegt... (sie definieren \(d\) durch die Gleichung \(n-1 = 2^sd\) mit d ungerade, und das \(r\) oben kommt aus \(\{0,1,\dots,s-1\}\)).
Freundliche Grüße,
Stefan
|
 Profil
|
ligning
Senior 
Dabei seit: 07.12.2014
Mitteilungen: 3525
Wohnort: Berlin
 | Beitrag No.1, eingetragen 2022-11-30
|
Hallo,
hier passiert nichts wildes, es wird einfach nur Modulo gerechnet. Ich nehme an, dass dir Kongruenzen und Restklassenringe grundsätzlich ein Begriff sind. Du scheinst aber nicht ganz so vertraut mit dem Rechnen mit Restklassen zu sein. Falls ich mich damit irre, bitte ich um Entschuldigung, dann musst du nochmal genauer nachfragen.
Ich hab das Buch nicht vorliegen, ich kenne allerdings den Rabin-Miller-Test ein wenig. Hier soll anscheinend für den Fall, dass $a^d\equiv 1\pmod{n}$ ist, ein Element aus $A$ gefunden werden, das potenziert mit $d$ kongruent zu $-1$ ist. Es gilt $(-a)^d \equiv (-1)^d a^d \equiv -1\cdot 1 \equiv -1\pmod{n}$, ist dir das soweit klar? Jetzt ist $-a$ aber in der Tat kein Element von $A$, so wie es dort definiert wurde.
Wenn du den Inhalt des Buches richtig wiedergegeben hast, ist das vielleicht ein bisschen ungenau aufgeschrieben. Was eigentlich gemeint ist: Um in $A$ ein Element $b$ mit $b^d \equiv -1\pmod{n}$ zu finden, sucht man ein Element in der Restklasse von $-a$, das auch in $A$ liegt. Zu $-a$ sind ja alle Elemente $-a + kn$, $k\in\IZ$, kongruent, so dass für alle davon gilt $(-a + kn)^d \equiv -1\pmod{n}$. Jetzt nimmt man sich einfach dasjenige, das auch in $A$ liegt, also $n-a$.
Es ist vielleicht günstiger, $A = \{ a\in (\IZ/n\IZ)^\times \mid n\text{ ist starke Pseudoprimzahl zur Basis }a\}$ zu setzen, dann bekommt man das alles kostenlos. $-a$ ist ja einfach das additive Inverse in $\IZ/n\IZ$.
[Verschoben aus Forum 'Strukturen und Algebra' in Forum 'Kongruenzen' von ligning]
|
Profil
|
stefanstiege
Wenig Aktiv
Dabei seit: 26.10.2020
Mitteilungen: 32
| Beitrag No.2, vom Themenstarter, eingetragen 2022-11-30
|
Hey!
Ja das war mir soweit geläufig, ich kam nur nicht auf die Idee, dass es einfach \(n-a\) ist... Danke!
Freundliche Grüße,
Stefan
|
Profil
|
stefanstiege hat die Antworten auf ihre/seine Frage gesehen.
stefanstiege 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
2023-03-24 11:03 U ?
Wie unterstütze ich den Matheplaneten mit Geld?
