multiplikatives inverses

22.01.2006, 17:22	Brox	Auf diesen Beitrag antworten »
multiplikatives inverses Wie berechne ich das multiplikative inverse von 17x=1 (mod 3^7) ohne dabei 3^7 ausrechnen zu müssen? Das Standardverfahren für sowas ist der erweiterte euklidische Algorithmus - aber ich hab nirgens ein Verfahren gefunden, dass die Faktorisierung von dem modul ausnutzt. Für die Leute die 3^7 unbedingt ausrechnen müssen: Hier die Frage nochmal für 17x=1 (mod 3^14)
22.01.2006, 17:43	Makukn	Auf diesen Beitrag antworten »
also 17 und 3 (und damit 17 und 3^7) sind ja nun teilerfremd und mit der Faktorisierung berechnet man leicht phi(modul), so dass man mit kleinem Fermat doch schon mal etwas weiß...
22.01.2006, 18:12	irre.flexiv	Auf diesen Beitrag antworten »
Statt einmal 3^7 auszurechnen und den erweiterten eukl. Alg. zu machen muss du dann $\begin{eqnarray} 17^{-1} \equiv 17^{23^6-1} \mod 3^7 \end{eqnarray*}$ bestimmen. Das spart nicht wirklich Arbeit aber es funktioniert =)
22.01.2006, 18:12	Brox	Auf diesen Beitrag antworten »
aber dann: x=17^(phi(3^7)-1)=17^(3^7-3^6-1)... Da finde ich 3^7 gleich auszurechnen und dann 17x=1 (mod 3^7) mit dem euklidischen algorithmus besser da man keine chance hat 17^dasda auszurechnen
22.01.2006, 18:29	Abar	Auf diesen Beitrag antworten »
ja, aber muss man denn 17 hoch dasda ausrechnen? kann man nicht die exponenten irgendiwe in beziehung setzen?
22.01.2006, 19:02	AD	Auf diesen Beitrag antworten »
Wie ich hier schon geschrieben hatte: $\begin{eqnarray} 17x \equiv 1 \mod 3^7 \end{eqnarray}$ bedeutet $\begin{eqnarray} 17x = 1 + 3^7 k \end{eqnarray}$ mit ganzzahligen $\begin{eqnarray} k \end{eqnarray}$ , was zu $\begin{eqnarray} 0 \equiv 1 + 3^7 k \equiv 1-6k\mod 17 \end{eqnarray}$ führt. Das kann man gut "zu Fuß" lösen (also probieren): $\begin{eqnarray} k = 3 \mod 17 \end{eqnarray}$ Ergebnis der Aufgabe ist dann $\begin{eqnarray} x \equiv \frac{1+3^8}{17} = 386 \mod 3^7 \end{eqnarray}$ . Der kleine Fermat ist ein gutes Hilfsmittel für Beweise, und auch zur Lösung einiger konkreter Kongruenzen sicherlich gut geeignet. Aber gerade für Kongruenzen $\begin{eqnarray} ax \equiv b \mod m \end{eqnarray}$ wo $\begin{eqnarray} m \end{eqnarray}$ deutlich größer als $\begin{eqnarray} a \end{eqnarray}$ ist (wie hier), ist er m.E. nach Overkill, wenn man an einer wirklich "lesbaren" Lösung der Kongruenz interessiert ist.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »