Rechenregeln modulare Arithmetik

08.04.2016, 13:11

KlausiMausi12345

Rechenregeln modulare Arithmetik

Meine Frage:
[1]
a) 283328383 mod 23838 = x
b) x mod 2883 = 292
c) 3837473 mod x = 2982

[2]
a) 338383 $\begin{eqnarray*} \equiv \end{eqnarray*}$ x mod 2238
b) 3485734 $\begin{eqnarray*} \equiv \end{eqnarray*}$ 2728 mod x

[3]
a) 3738937^x mod 2837 = 271
b) $\begin{eqnarray*} x^{28383} \end{eqnarray*}$ mod 398 = 281

[4]
a) 3738937^x $\begin{eqnarray*} \equiv \end{eqnarray*}$ 3453 mod 2837
b) $\begin{eqnarray*} 3738937^{8338} \end{eqnarray*}$ $\begin{eqnarray*} \equiv \end{eqnarray*}$ x mod 2837

Meine Ideen:
Hallo!

Es gibt bei der modularen Arithmetik ein paar Rechenaufgaben, bei denen ich nicht ganz sicher bin, wie man da am schnellsten zum Ergebnis kommt. Ich habe extra große Zahlen gewählt, weil man bei kleine Zahlen ja oft leicht im Kopf rechnen kann.

[1]
a) Wie findet man das am schnellsten? Euklidischer Algorithmus?
b) Hier muss man ja rechnen x = k*2883 + 292, oder? Wie geht man da am besten vor?
c) Hier lautet die Gleichung: 3837473 = k*x + 2982, richtig? Wie geht man denn hier vor?

[2]
a) Hier muss man ja rechnen: 338383 mod 2238 = x mod 2238, oder? links wieder der Euklid. Alg. und rechts so wie in Aufgabe [1] b).
b) Hier muss man lösen: 3485734 mod x = 2728 mod x, also wie in Aufgabe [1] c.

[3]
a) Wie löst man sowas? Hab da gar keinen Ansatz
b) Ebenso... keinen Plan.

[4]
a) Das ist ja der diskrete Logarithmus. Da weiß ich, wie man den schnell löst ;-)
b) Das kann man umformen zu $\begin{eqnarray*} 3738937^{8338} \end{eqnarray*}$ mod 2837 = x mod 2837, dann gilt für die rechte Seite wieder dasselbe wir in [1] b.

Stimmen die Ansätze soweit?

Mir geht es bei allen Ansätzen darum, wie man das bei großen Zahlen schnell macht.

08.04.2016, 18:21

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von KlausiMausi12345
a) Wie findet man das am schnellsten? Euklidischer Algorithmus?

Division mit Rest, und letzterer ist hier ja gesucht.

Zitat:

Original von KlausiMausi12345
b) Hier muss man ja rechnen x = k*2883 + 292, oder? Wie geht man da am besten vor?

Was willst du denn noch weiter "vorgehen"? k*2883 + 292 ist die Lösung, mit beliebigem ganzzahligen k. Augenzwinkern

Zitat:

Original von KlausiMausi12345
c) Hier lautet die Gleichung: 3837473 = k*x + 2982, richtig? Wie geht man denn hier vor?

Nun, die 2982 kannst du durch Subtrahieren rüber bringen. Dann steht da ein Produkt k*x, welches gleich einer festen, dir bekannten Zahl sein soll ... da kann es je nach Primfaktorzerlegung dieser Zahl eine ganze Menge Lösungen geben. Allerdings kommen davon nur Werte x>2982 in Frage, weil für kleinere ja nicht der Rest 2982 entstehen kann.

08.04.2016, 20:13

KlausiMausi12345

Auf diesen Beitrag antworten »

Hallo HAL 9000

Klar, ich Depp, da geht ja jedes k Big Laugh

Danke soweit mal!

Wie wäre es bei 3 a) und b)? Da ist ja nicht die Kongruenz gesucht, sondern der Wert. Wie ist da der Ansatz?

09.04.2016, 10:48

HAL 9000

Auf diesen Beitrag antworten »

Zu 3a) 2837 ist Primzahl, und es ist $\begin{align*} 3738937\equiv 2608\bmod 2837 \end{align*}$ . Nach kleinem Fermat ist mit jeder Lösung $\begin{align*} x \end{align*}$ auch die gesamte Restklasse $\begin{align*} x\bmod 2836 \end{align*}$ Lösung.

Was die Bestimmung eines $\begin{align*} x \end{align*}$ angeht (bzw. ob es überhaupt eines gibt): Ich hab nicht sonderlich viel Ahnung von Algorithmen zur Berechnung des diskreten Logarithmus, ich weiß nur, dass sie sämtlich nicht sonderlich schnell sind. Bei Primmodul 2837 kann man natürlich primitiverweise alle 2836 Exponenten $\begin{align*} x=0,1,\ldots,2835 \end{align*}$ durchprobieren, zumindest mit rechentechnischer Unterstützung. Augenzwinkern

Zu 3b) Zunächst die Primfaktorzerlegung des Moduls: $\begin{align*} 398 = 2\cdot 199 \end{align*}$ .

Modulo 2 muss daher $\begin{align*} x^{28383}\equiv 1\bmod 2 \end{align*}$ gelten, also $\begin{align*} x\equiv 1\bmod 2 \end{align*}$ .

Modulo 199 haben wir via kleinem Fermat $\begin{align*} x^{28383}\equiv x^{69}\equiv 82\bmod 199 \end{align*}$ , wegen $\begin{align*} 28383\equiv 69\bmod 198 \end{align*}$ . Und wieder fällt mir da erstmal nix besseres ein, als per Brute-Force alle $\begin{align*} x\bmod 199 \end{align*}$ durchzuprobieren...

Neue Frage »

Antworten »

Rechenregeln modulare Arithmetik

Verwandte Themen