Rechnen mit Restzahlen - Rechenregeln mit Resten

16.10.2008, 01:49

schubi

Rechnen mit Restzahlen - Rechenregeln mit Resten

Hallo

Ich bin Schüler des KAV-Gymnasiums in Celle und soll im Rahmen des Informatikunterrichts ein Referat über die RSA Verschlüsselung inklusive sämtlicher Beweise halten.
Eine gute Anleitung mit Beweisen habe ich hier gefunden:
http://www.uni-giessen.de/~g013/code/rsa2.pdf

Auf Seite 4 und 5 werden Rechenregeln für das Rechnen mit Resten aufgeführt und bewiesen.

Beim Beweis (zu Satz 11) steht, dass man durch Addition (x+y) - (x'+y') = (k+l) * m erhält. (Seite 5 (4) )

Soweit so gut, dann aber steht im nächsten Satz, dass daraus Gleichung (1) folgt, also x+y =m= x'+y'. Wieso ist das so? Wie kann man das denn daraus entnehmen?

Mit freundlichen Grüßen

schubi

---edit---

x+y =m= x'+y'
Diese Schreibweise bedeutet das gleiche wie
x+y%m = x'+y'%m

16.10.2008, 07:30

Airblader

Auf diesen Beitrag antworten »

Die Addition der Gleichungen bei (4) sagt ja aus, dass (x+y)-(x'+y') restlos durch m teilbar ist.
Das heißt:

$\begin{eqnarray*} (x+y)-(x'+y') = 0\qquad \mod m \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow~x+y = x'+y'\qquad \mod m \end{eqnarray*}$

air

16.10.2008, 11:48

schubi

Auf diesen Beitrag antworten »

Ich weiß nciht ganz genau ob ich diene Schreibweise verstanden habe ... Kannst du mich nochmal korrigieren? smile

$\begin{eqnarray*} ((x+y)-(x'+y')) \mod m = 0 \end{eqnarray*}$
$\begin{eqnarray*} (x+y) \mod m = (x'+y') \mod m \end{eqnarray*}$

Daraus folgt ja, dass man das Modulo sozusagen aufteilen kann... Also man hat zwei Terme die zusammen mit Modulo m = 0 ergeben, somit ergibt jeder Term für sich genommen den gleichen Rest durch m geteilt wie der andere ... warum folgt das? Ich versteh das noch nicht so richtig ...

Vielen Dank für deine Antwort smile

---edit---
Um es nochmal präzise zu sagen:
Ich weiß, dass aus der Bedingung bei (4) das folgt:
$\begin{eqnarray*} ((x+y)-(x'+y')) \mod m = 0 \end{eqnarray*}$

aber nicht wie man daraus auf
$\begin{eqnarray*} (x+y) \mod m = (x'+y') \mod m \end{eqnarray*}$
schließen kann.

16.10.2008, 11:55

schubi

Auf diesen Beitrag antworten »

Also ich hab mir das anhand von einen paar Zahlenbeispielen verdeutlicht, dass gilt:
$\begin{eqnarray*} x+y \mod m = 0 \end{eqnarray*}$
und daraus folgt
$\begin{eqnarray*} x \mod m = y \mod m \end{eqnarray*}$

Nur, ist es auch bewiesen? Ich meine, ja mansieht das es hinkommt, aber kann man das auch wirklich allgemein sagen? Ich muss das doch beweisen oder nicht? smile

16.10.2008, 13:18

ajax2leet

Auf diesen Beitrag antworten »

Die Äquivelnz $\begin{eqnarray*} x \mod m = 0 \Leftrightarrow m \mid x \Leftrightarrow \exists a \in \mathbb N : m \cdot a = x \end{eqnarray*}$ sollte dir helfen smile

Mir hat mal der wikipedia-Eintrag http://de.wikipedia.org/wiki/RSA-Kryptosystem sehr geholfen.
Das Prinzip ist gut erklärt und alle wichtigen Begriffe auf die entsprechenden Artikel verlinkt.

16.10.2008, 15:43

schubi

Auf diesen Beitrag antworten »

Naja, dass das gilt ist mir klar! Die "Herleitung" zu der Form

$\begin{eqnarray*} (x+y)-(x'+y') = 0 \mod m \end{eqnarray*}$

erfolgte ja über die Formel:

$\begin{eqnarray*} (x+y)-(x'+y') = (k+l) * m \end{eqnarray*}$

Diese impliziert ja schon die Bedingung bzw. den Zusammenhang den du aufgestellt hast, also:

$\begin{eqnarray*} x \mod m = 0 \Leftrightarrow m \mid x \Leftrightarrow \exists a \in \mathbb N : m \cdot a = x \end{eqnarray*}$

Nur irgendwie weiß ich grad nciht ob ich einfach zu doof bin um den Zusammenhang zwischen
$\begin{eqnarray*} (x+y)-(x'+y') = 0\qquad \mod m \end{eqnarray*}$
und
$\begin{eqnarray*} \Leftrightarrow~x+y = x'+y'\qquad \mod m \end{eqnarray*}$

zu sehen oder ich kann mich nicht richtig ausdrücken ... ^^ Hat noch wer einen Vorschlag wie man mir auf die Sprünge helfen könnte? smile

Vielen Dank smile

16.10.2008, 15:52

schubi

Auf diesen Beitrag antworten »

Hm okay, ich glaube mir haben einfach nur gewisse Rechenregeln für den Umgang mit modulo-Operationen gefehlt.

Also stimtm es das ich beispielsweise aus

$\begin{eqnarray*} x+y \mod m = 0 \end{eqnarray*}$

$\begin{eqnarray*} x \mod m + y \mod m = 0 \end{eqnarray*}$

machen kann?

Ich also beliebig umformen darf mit modulo Operationen? Oder gibt es Einschränkungen?

16.10.2008, 17:44

ajax2leet

Auf diesen Beitrag antworten »

Zitat:

Original von schubi
Also ich hab mir das anhand von einen paar Zahlenbeispielen verdeutlicht, dass gilt:
$\begin{eqnarray*} x+y \mod m = 0 \end{eqnarray*}$
und daraus folgt
$\begin{eqnarray*} x \mod m = y \mod m \end{eqnarray*}$

Nur, ist es auch bewiesen? Ich meine, ja mansieht das es hinkommt, aber kann man das auch wirklich allgemein sagen? Ich muss das doch beweisen oder nicht? smile

Ich hab mich vorhin verguckt!
Gegenbeispiel: $\begin{eqnarray*} 7+3 \mod 5 = 0 \end{eqnarray*}$
$\begin{eqnarray*} 7 \mod 5 = 2 \end{eqnarray*}$
$\begin{eqnarray*} 3 \mod 5 = 3 \end{eqnarray*}$

Zu deiner Frage oben:

Zitat:

Original von schubi
---edit---
Um es nochmal präzise zu sagen:
Ich weiß, dass aus der Bedingung bei (4) das folgt:
$\begin{eqnarray*} ((x+y)-(x'+y')) \mod m = 0 \end{eqnarray*}$

aber nicht wie man daraus auf
$\begin{eqnarray*} (x+y) \mod m = (x'+y') \mod m \end{eqnarray*}$
schließen kann.

Nun, wenn m die Differenz a-b teilt, dann gibt es ein k, sodass a = k*m + b

b habe bei der der Division durch m nun den Rest c.
Also gilt b = q*m + c

Kommst du damit weiter?

16.04.2009, 18:05

MRWN

Auf diesen Beitrag antworten »

hab mal ne frage dazu Big Laugh

auch wegen so rechnen mit resten..

und zwar hab ich dies hier:

x_(n+1) = K*x_n mod m

^^ wie kann ich die denn so umformen das ich x_n berechnen kann? ....nen Link zu einem Tutorium oder ne direkte Antworte wären schon sehr hilfreich. Ist nix wegen schule und so - interessiert mich einfach smile

Matt

16.04.2009, 18:25

kiste

Auf diesen Beitrag antworten »

Direkte Antwort: gar nicht. $\begin{eqnarray*} x_n \end{eqnarray*}$ ist bei gegebenen $\begin{eqnarray*} x_{n+1},K,m \end{eqnarray*}$ nicht eindeutig

16.04.2009, 19:19

MRWN

Auf diesen Beitrag antworten »

also ^^ abgesehen davon das ich das nun nicht so richtig verstehe.....

Ich verfolg einfach mal deine Aussage Big Laugh

:

Wenn x_(n+1) gegeben ist,
wenn K gegeben ist und
wenn m gegeben ist,

so bleibt x_n absolut unbekannt xD?

Ich frag nur weil mir nen Kumpel ne rechnung vorgelegt hat und ich nix damit so richtig anfangen konnte.

Die rechnung sah so aus:

x_(n+1) = 16807*x_n mod ((2^31) - 1)

Aufgabe:
Wenn x_1 = maximum ist, sprich ((2^31) - 2), wie könnte dann x_0 aussehen? xD

Also ich bin im zweiten Semester meines Informatikstudiums....und ehrlich ich wusste einfach net was zu tun ist (Bin auch kein wirklicher Matheprofi)....

xD Matt

16.04.2009, 21:20

kiste

Auf diesen Beitrag antworten »

Ich will mal nicht so sein und dir trotzdem etwas helfen.

Meine Aussage dass $\begin{eqnarray*} x_0 \end{eqnarray*}$ nicht eindeutig bestimmbar ist stimmt weiterhin. Es lässt sich jedoch die gesamte Lösungsmenge bestimmen Big Laugh

. Wahrscheinlich meinte dein Kumpel die Lösung die zwischen 0 und 2^31-2 liegt Augenzwinkern

.

Das ganze lässt sich relativ einfach(relativ da man hier wenn man sich nicht todrechnen will pc-unterstützung besser benutzt aber das sollte als Informatiker ja kein Problem sein) berechnen.

Da ggT(16807,2^31-1)=1 ist existieren nach dem Lemma von Bezout Koeffizienten a,b so dass $\begin{eqnarray*} 16807a+(2^{31}-1)b = 1 \end{eqnarray*}$ gilt. Deine Aufgabe ist es nun a zu bestimmen.

Berechnest du nun $\begin{eqnarray*} a\cdot (2^{31}-2) \mod 2^{31}-1 \end{eqnarray*}$ so ergibt sich die Basislösung $\begin{eqnarray*} x_0 \end{eqnarray*}$ . Die gesamte Lösungsmenge ist dann $\begin{eqnarray*} \{x_0 + k\cdot (2^{31}-1) \mid k\in \mathbb Z\} \end{eqnarray*}$

Neue Frage »

Antworten »

Rechnen mit Restzahlen - Rechenregeln mit Resten

Verwandte Themen