Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Beweis zum Miller-Rabin-Test unverständlich
Autor
Universität/Hochschule J Beweis zum Miller-Rabin-Test unverständlich
stefanstiege
Aktiv Letzter Besuch: im letzten Quartal
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 Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3519
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
Aktiv Letzter Besuch: im letzten Quartal
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.

Wechsel in ein anderes Forum:
 Suchen    
 
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]