Frage zu Modulo mit Multiplikation

09.05.2013, 23:57

eey

Frage zu Modulo mit Multiplikation

Hallo zusammen,

gibt es eine Möglichkeit so etwas hier

$\begin{eqnarray*} 71356\cdot 61234 \operatorname{mod} 82577 = 16503 \end{eqnarray*}$

zu rechnen ohne die Multiplikation so wie sie da steht auszuführen? Ich hab es schon so probiert:

$\begin{eqnarray*} 71356\cdot 61234 \operatorname{mod} 82577 = ((71356 \operatorname{mod} 82577) \cdot 61234) \operatorname{mod} 82577 \end{eqnarray*}$

Aber das bringt mir leider nichts, weil durch den großen Modulus dann wieder die gleiche Multiplikation da steht....

Gibt es einen Trick das zu vermeiden, so dass man mit kleineren Zahlen rechnen kann?

Schöne Grüße,
eey

10.05.2013, 00:02

watcher

Auf diesen Beitrag antworten »

Hallo,

die Standardschreibweise ist, da deutlich übersichtlicher:

$\begin{eqnarray*} a \cdot b \equiv c \mod n \end{eqnarray*}$

Hier bittet es nicht an als Repräsentanten der Restklassen $\begin{eqnarray*} \{-\frac{p-1}{2}, \ldots , 0, \ldots ,\frac{p-1}{2} \} \end{eqnarray*}$ zu verwenden.

10.05.2013, 00:07

eey

Auf diesen Beitrag antworten »

Hallo,

danke schonmal für die Antwort!

Zitat:

Original von watcher
Hier bittet es nicht an als Repräsentanten der Restklassen $\begin{eqnarray*} \{-\frac{p-1}{2}, \ldots , 0, \ldots ,\frac{p-1}{2} \} \end{eqnarray*}$ zu verwenden.

Das versteh ich noch nicht ganz... meinst du es bietet sich an oder es bietet sich nicht an? Und wie bekomme ich effektiv diese Restklassen?

Schöne Grüße,
eey

10.05.2013, 00:11

watcher

Auf diesen Beitrag antworten »

Sorry, Tippfehler wohl heute schon zu spät.
Es bietet sich an.

Wie du diese Darstellung kriegst. Sehr schnell, sehr banal. Bitte etwas drüber nachdenken, ist nicht schwer.

10.05.2013, 14:32

eey

Auf diesen Beitrag antworten »

Hallo nochmal,

also ich bin mir nicht sicher ob ich es richtig verstanden habe, aber ich hab es jetzt erstmal so gemacht:

$\begin{eqnarray*} 71356 \cdot 61234 \equiv 16503 \mod 82577 \end{eqnarray*}$

$\begin{eqnarray*} = (71356 - 82577) \cdot (61234 - 82577) \equiv 16503 \mod 82577 \end{eqnarray*}$

$\begin{eqnarray*} = -11221 \cdot -21343 \equiv 16503 \mod 82577 \end{eqnarray*}$

Damit bin ich jetzt von einer Multiplikation von 71356*61234 auf eine Multiplikation von -11221 *(-21343) runtergekommen. In diesem Fall ist das Ok und alles funktioniert wie gewünscht.

Problematisch wirds allerdings bei noch größeren Zahlen, wie zum Beispiel:

$\begin{eqnarray*} 111738 \cdot 111738 \equiv 133592 \mod 169241 \end{eqnarray*}$

Wenn ich hier genauso wie oben vorgehe erhalte ich:

$\begin{eqnarray*} (111738 - 169241) \cdot (111738 - 169241) \equiv 133592 \mod 169241 \end{eqnarray*}$

$\begin{eqnarray*} \underbrace{-57503 \cdot -57503}_{\text{Wieder zu groß}} \equiv 133592 \mod 169241 \end{eqnarray*}$

Gibt es noch weitere Möglichkeiten die Multiplikation zu verkleinern oder hab ich das mit den Restklassen falsch verstanden?

Schöne Grüße,
eey

10.05.2013, 14:42

watcher

Auf diesen Beitrag antworten »

Schaut alles richtig aus.

Im Allgemeinen gibt es keinen weiteren Weg "die Multiplikation zu verkleinern".

Also was ist die eigentliche Frage, bzw. wieso ist die Multiplikation zweier (dezimal) 5-stelliger Zahlen schon zu "groß"?
Int ist hier kein geeigneter Datentyp.

10.05.2013, 15:00

eey

Auf diesen Beitrag antworten »

Das Problem ist, dass ich in einer Sprache programmiere die nur single Genauigkeit hat (egal welcher Datentyp).

Das heißt dass keine Zahlen größer als 2147483647 verwendet werden können.

$\begin{eqnarray*} -11221 \cdot (-21343) = 239489803 \rightarrow \text{korrekt} \end{eqnarray*}$

wird korrekt berechnet. 57503*57503 ist aber größer als 2147483647 und führt zu folgendem:

$\begin{eqnarray*} 57503 \cdot 57503 = -988372287 \rightarrow \text{falsch!} \end{eqnarray*}$

Also heißt das ich hab keine Chance da noch irgendwas zu drehen?

Schöne Grüße,
eey

10.05.2013, 15:05

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von eey
Das heißt dass keine Zahlen größer als 2147483647 verwendet werden können.

Also "nur" 32 Bit. Steig mal auf 64 Bit um, bzw. wenn du öfters mit so großen Zahlen opererieren willst, dann schau dich gleich mal nach einer Bibliothek wie z.B. der GMP

http://gmplib.org/

um. Augenzwinkern

10.05.2013, 15:13

eey

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Also "nur" 32 Bit. Steig mal auf 64 Bit um

Das geht leider nicht Big Laugh

Das Ganze ist innerhalb einer eingebetteten Programmiersprache einer Uralten Anwendung...
Leider hab ich nur 32 bit oder Strings zur Verfügung. unglücklich

Ich könnte das alles auch mit Strings machen (also sowas wie ne BigInt Klasse), aber das ist natürlich um mehrere Größenordnungen langsamer. Daher wollte ich erstmal schauen ob es noch irgendwelche Tricks gibt sowas zu berechnen.

10.05.2013, 15:27

HAL 9000

Auf diesen Beitrag antworten »

Na dann rechne doch so, wie man immer rechnet, wenn die Bitbreite nicht ausreicht:

Wähle irgendein "Zwischenmodul" $\begin{eqnarray*} z \end{eqnarray*}$ , dessen Quadrat noch in deinen Zahlbereich passt, vorzugsweise eine Zweierpotenz, passend wäre hier $\begin{eqnarray*} z=2^{15} = 32768 \end{eqnarray*}$ .

Nun gilt für das Produkt von $\begin{eqnarray*} a=rz+u \end{eqnarray*}$ und $\begin{eqnarray*} b=vz+w \end{eqnarray*}$

$\begin{eqnarray*} ab = rvz^2 + (rw+uv)z + uw \end{eqnarray*}$

sowie dann

$\begin{eqnarray*} ab \bmod m = ((rv \bmod m) (z^2 \bmod m) + ((rw+uv) \bmod m) z + (uw \bmod m)) \bmod m \end{eqnarray*}$ .

So oder ähnlich kannst du das doch herunterbrechen. Ist übrigens kein "Trick", sondern absolutes Standardvorgehen.

P.S.: Ist natürlich irgendwie saublöd, dass dein Modul $\begin{eqnarray*} m=82577 \end{eqnarray*}$ die Eigenschaft hat, dass bereits dessen Quadrat deinen Zahlbereich überschreitet. Das macht deine einengende Programmiersprache irgendwie ungeeignet für dein Ansinnen, noch dazu, da du anscheinend auch noch Performance brauchst (wenn Emulationen wie BigInt dir "zu langsam" sind).

10.05.2013, 16:25

eey

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Na dann rechne doch so, wie man immer rechnet, wenn die Bitbreite nicht ausreicht:

Wähle irgendein "Zwischenmodul" $\begin{eqnarray*} z \end{eqnarray*}$ , dessen Quadrat noch in deinen Zahlbereich passt, vorzugsweise eine Zweierpotenz, passend wäre hier $\begin{eqnarray*} z=2^{15} = 32768 \end{eqnarray*}$ .

Nun gilt für das Produkt von $\begin{eqnarray*} a=rz+u \end{eqnarray*}$ und $\begin{eqnarray*} b=vz+w \end{eqnarray*}$

$\begin{eqnarray*} ab = rvz^2 + (rw+uv)z + uw \end{eqnarray*}$

sowie dann

$\begin{eqnarray*} ab \bmod m = ((rv \bmod m) (z^2 \bmod m) + ((rw+uv) \bmod m) z + (uw \bmod m)) \bmod m \end{eqnarray*}$ .

Sowas in der Art hab ich gesucht, sieht schonmal sehr vielversprechend aus, danke Freude

Zitat:

Original von HAL 9000
So oder ähnlich kannst du das doch herunterbrechen. Ist übrigens kein "Trick", sondern absolutes Standardvorgehen.

Ja, ich kenn mich mit modulo Rechnung eigentlich überhaupt nicht aus (hab das noch nie gebraucht bis jetzt)... Mein bisschen "Wissen" hab ich mir nur aus Wikipedia zusammen gesucht Big Laugh

Zitat:

Original von HAL 9000
P.S.: Ist natürlich irgendwie saublöd, dass dein Modul $\begin{eqnarray*} m=82577 \end{eqnarray*}$ die Eigenschaft hat, dass bereits dessen Quadrat deinen Zahlbereich überschreitet. Das macht deine einengende Programmiersprache irgendwie ungeeignet für dein Ansinnen, noch dazu, da du anscheinend auch noch Performance brauchst (wenn Emulationen wie BigInt dir "zu langsam" sind).

Ich probier mal deinen Vorschlag aus, vielleicht reicht das ja schon...

Schöne Grüße,
eey

Neue Frage »

Antworten »

Frage zu Modulo mit Multiplikation

Verwandte Themen