Diskrete Strukturen < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:27 Mi 20.11.2013 | | Autor: | infaktor |
| Aufgabe | Zeigen Sie, dass folgenden Aussagen gültig sind!
a) (a + b) mod n = (a mod n) + (b mod n) mod n
b) [mm] a^d [/mm] mod n = [mm] (a^{d-x}*a^x) [/mm] mod n = [mm] ((a^{d-x} [/mm] mod [mm] n)*(a^x [/mm] mod n)) mod n |
Wie genau kann ich jetzt die Gültigkeit beweisen bzw. wie sollte ich an das Problem herangehen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:08 Mi 20.11.2013 | | Autor: | Ebri |
Hi,
sagt dir das hier etwas:
Für [mm] a\in\IZ [/mm] und [mm] n\in\IN [/mm] mit n > 0 ist
a mod n := a - [mm] \lfloor [/mm] a/n [mm] \rfloor*n
[/mm]
Ebri
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:57 Mi 20.11.2013 | | Autor: | infaktor |
Leider nicht wirklich viel. Kann ich paar Kommentare dazu bitten?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:38 Mi 20.11.2013 | | Autor: | Ebri |
> Leider nicht wirklich viel. Kann ich paar Kommentare dazu
> bitten?
Das ist die Definition (bzw. ein Teil davon) von Modulo (mod) als Funktion.
Sie berechnet den Rest einer Division zweier Zahlen. Zum Beispiel 13 mod 5 = 3. Aber ich denke das ist soweit klar.
Daran habe ich spontan gedacht, vielleicht ist das nicht die gewünschte oder beste Herangehensweise, aber a) habe ich damit zeigen können
( b) habe ich nicht probiert ).
![[]](/images/popup.gif) Genaueres zu der Funktion hier.
Ebri
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:56 Mi 20.11.2013 | | Autor: | felixf |
Moin!
> Zeigen Sie, dass folgenden Aussagen gültig sind!
> a) (a + b) mod n = (a mod n) + (b mod n) mod n
Eine andere Moeglichkeit, an das Problem heranzugehen, ist erstmal $a = [mm] q_1 [/mm] n + [mm] r_1$ [/mm] und $b = [mm] q_2 [/mm] n + [mm] r_2$ [/mm] mit $0 [mm] \le r_i [/mm] < n$ und [mm] $q_i, r_i \in \IZ$ [/mm] zu schreiben. Dann ist [mm] $r_1 [/mm] = a [mm] \bmod [/mm] n$ und [mm] $r_2 [/mm] = b [mm] \bmod [/mm] n$. Damit musst du dir ueberlegen, warum $(a + b) [mm] \bmod [/mm] n = [mm] (r_1 [/mm] + [mm] r_2) \bmod [/mm] n$ ist.
> b) [mm]a^d[/mm] mod n = [mm](a^{d-x}*a^x)[/mm] mod n = [mm]((a^{d-x}[/mm] mod
> [mm]n)*(a^x[/mm] mod n)) mod n
Hier reicht es aus, $(a [mm] \cdot [/mm] b) [mm] \bmod [/mm] n = ((a [mm] \bmod [/mm] n) [mm] \cdot [/mm] (b [mm] \bmod [/mm] n)) [mm] \bmod [/mm] n$ zu zeigen. Der Rest folgt aus allgemeingueltigen Rechenregeln. Auch hier kannst du wie in a) vorgehen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:59 Mi 20.11.2013 | | Autor: | felixf |
Und noch ein Hinweis:
> a) (a + b) mod n = (a mod n) + (b mod n) mod n
das wurde die Tage bereits hier diskutiert.
LG Felix
|
|
|
|
