Modulo-Rechnung

10.07.2006, 09:59	guest	Auf diesen Beitrag antworten »
Modulo-Rechnung Hallo. Habe folgendes Problem. Wie kann ich z.B. 3242^43 mod 22 rechnen? Gruß
10.07.2006, 10:22	andre81	Auf diesen Beitrag antworten »
Wahrscheinlich kannst du das gar nicht berechnen, da bei 3242^43 schon die Rechengenauigkeit nicht mehr hinhaut! Das einzige was du versuchen kannst, ist dir ein C oder Java PRog zu schreiben, dass dir das berechnet, aber kann dir keine Garantie geben, dass es dann richtig ist! Zahlen sind einfach zu groß für Standardrechner (Taschenrechner, Excel, ect.)! Gruß André
10.07.2006, 10:33	andre81	Auf diesen Beitrag antworten »
hab grad mal nachgeschaut! Mit C gehts nicht! Wenn man den max. möglichen Datentyp nimmt: long double hat 80 Bit Darstellung in einem Wertebereich von ca. ± 3.410^-4932 bis ± 3.410^+4932 mit einer maximalen Auflösung von 19 Stellen! Für deine Aufgabe brauchst du schätzungsweise eine GEnauigkeit von 150 oder mehr Stellen. Also denke ich mal: MISSION IMPOSSIBLE! gruß andre
10.07.2006, 10:45	papahuhn	Auf diesen Beitrag antworten »
Mit brachialer Rechenleistung kommste nicht weit. Aber so war die Aufgabe wahrscheinlich gar nicht gemeint. Ich würde mal abwarten, bis einige Algebraiker vorbeikommen die dir das erklären können. Ich bin da leider nicht so firm drin, aber ich tippe mal auf 6. Vielleicht kann ich Dir doch erklären wie das geht. Das Warum übernimmt dann ein anderer. Das Modulo kannst du praktisch in die Basis reinziehen. Dadurch verkleinert sich die Zahl immer weiter. $\begin{eqnarray} 3242 \equiv 8 (mod\ 22) \Rightarrow {3242}^{43} \equiv 8^{43} (mod\ 22) \end{eqnarray}$ . Dadurch kannst du die Basis wieder vergrößern: $\begin{eqnarray} 8^{43} \equiv 88^{42} \equiv 8{64}^{21} \equiv 8{20}^{21} (mod\ 22) \end{eqnarray*}$ . Das machst du solange weiter, bis es nicht mehr geht.
10.07.2006, 11:44	AD	Auf diesen Beitrag antworten »
Oder so: An papahuhn anknüpfend, kann man so rechnen $\begin{eqnarray} x := 3242^{43} \equiv 8^{43} = (2^3)^{43}=2^{129} \mod 22 \end{eqnarray}$ Jetzt nach Primzahlpotenz-Modulen trennen: $\begin{eqnarray} x\equiv 2^{129} \equiv 0 \mod 2 \end{eqnarray}$ , und wegen des kleinen Fermats $\begin{eqnarray} 2^{10} \equiv 1\mod 11 \end{eqnarray}$ folgt $\begin{eqnarray} x\equiv 2^{129} \equiv 2^9 = 512 \equiv 6 \mod 11 \end{eqnarray}$ Jetzt wieder modulo 22 zusammenbauen: $\begin{eqnarray} x \equiv 6 \mod 11 \end{eqnarray}$ und $\begin{eqnarray} x \equiv 0 \mod 2 \end{eqnarray}$ ergibt $\begin{eqnarray} x\equiv 6 \mod 22 \end{eqnarray}$ . Ist einerseits aufwändiger wegen der Modulaufspaltung und -wiederzusammenführung. Andererseits sind die Teilrechnungen modulo 2 und 11 um einiges einfacher.
10.07.2006, 12:28	Evok	Auf diesen Beitrag antworten »
such mal nach dem satz von euler-fermat
Anzeige

10.07.2006, 15:12	guest	Auf diesen Beitrag antworten »
Danke schon mal für eure Antworten. Leider kapier ich das immer noch nicht! Eine Konkrete Aufgabe ist: 348^47 mod 5917 Komm nicht drauf wie man das umrechnet
10.07.2006, 16:00	AD	Auf diesen Beitrag antworten »
Ok, hier nützt Fermat vermutlich wirklich nicht viel, weil der Exponent vergleichsweise klein ist in Relation zum Modul. Systematisch geht man in solchen Fällen eher so vor: Du erstellst eine Binärdarstellung des Exponenten, in unserem Fall $\begin{eqnarray} 47 = 32+8+4+2+1 = 2^5+2^3+2^2+2^1+2^0=[101111]_2 \end{eqnarray}$ . Dann gilt ja $\begin{eqnarray} 348^{47} = 348^{2^5}\cdot 348^{2^3}\cdot 348^{2^2}\cdot 348^{2^1}\cdot 348^{2^0}\qquad () \end{eqnarray}$ Und dann kannst du die benötigten Potenzen - genauer gesagt deren Restklassen modulo 59127 - rekursiv berechnen: $\begin{eqnarray} 348^1 &\equiv& 348\mod 5917\\ 348^2 &=& 121104 \equiv 2764\mod 5917\\ 348^4 &\equiv& 2764^2 = 7639696 \equiv 849\mod 5917\\ 348^8 &\equiv& 849^2 = 720801 \equiv 4844\mod 5917 \end{eqnarray}$ usw. Abschließend multiplizierst du die gemäß () benötigten Werte. P.S.: Im Einzelfall geht es sehr oft auch eleganter, aber wenn einem das Auge dazu fehlt, sollte man lieber wie beschrieben systematisch vorgehen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »