________________________________________________________________________________
Inhalt....: Modulares Rechnen
Kategorie.: Handwerkskasten
Mathematik: Zahlentheorie, Kryptographie
MuPAD.....: 3.0.0
Datum.....: 2002-08-14
Autoren...: Kai Gehrs <acrowley@mupad.de>
Funktionen: div, mod, powermod
________________________________________________________________________________
Elementare MuPAD-Funktionen:
Modulares Rechnen
Das modulare Rechnen wird insbesondere in kryptographischen Anwendungen ständig benötigt.
Aus diesem Grund sollen hier die wichtigsten Funktionen 'div', 'mod' und 'powermod' vorgestellt
werden.
Mit Hilfe der MuPAD Funktion mod läßt sich der nichtnegative Rest bei der
Division zweier ganzer Zahlen berechnen.
Die Funktion mod kann so verwendet werden, wie man es von den üblichen
Operatoren +, -, * und / in MuPAD gewohnt ist, d.h. die Funktion erhält nicht
wirklich Argumente als Eingabe.
Ein Aufruf der Form a mod b für ganze Zahlen a und b berechnet als Rück-
gabewert den nichtnegativen Rest bei ganzzahliger Division von a durch b.
Die Handhabung der Funktion ist also denkbar einfach. Wir betrachten einige
Beispiele und machen jeweils auch die Probe:
10 mod 3
Denn es gilt:
10 = 3 * 3 + 1
10 mod 4
Denn es gilt:
10 = 2 * 4 + 2
10 mod 5
Denn gilt:
10 = 2 * 5 + 0
Zusätzlich ist es möglich, die Funktion _mod zu verwenden. Sie ist sozusagen
die "funktionale Variante" zu dem "Operator" mod.
Die Funktion _mod erhält stets zwei Argumente:
1. Argument: Eine ganze Zahl a
2. Argument: Eine ganze Zahl b
d.h. also ein Aufruf ist immer von der Form _mod( a, b ).
Als Rückgabewert liefert uns die Funktion _mod ebenfalls den nichtnegativen
ganzzahligen Rest bei Division von a durch b.
Wir berechnen die gleichen Reste wie oben nun mit Hilfe der Funktion _mod:
_mod(10, 3)
_mod(10, 4)
_mod(10, 5)
Wenn wir den Rest bei ganzzahliger Division zweier Zahlen berechnen können,
so möchten wir unter Umständen auch den Quotienten der beiden Zahlen
bestimmen. Diesem Zweck dient der Operator div bzw. die Funktion _div.
Die Verwendung ist ganz analog zu der von mod bzw. _mod.
Die Funktion div kann so verwendet werden, wie man es von den üblichen
Operatoren +, -, * und / in MuPAD gewohnt ist, d.h. die Funktion erhält nicht
wirklich Argumente als Eingabe.
Ein Aufruf der Form a div b für ganze Zahlen a und b berechnet als Rückgabewert
den ganzzahligen Quotienten von a und b.
10 div 3
Denn es gilt:
10 = 3 * 3 + 1
10 div 4
Denn es gilt:
10 = 2 * 4 + 2
10 div 5
Denn es gilt:
10 = 2 * 5 + 0
Analog beschreiben wir die Funktion _div:
Die Funktion _div erhält stets zwei Argumente:
1. Argument: Eine ganze Zahl a
2. Argument: Eine ganze Zahl b
d.h. also ein Aufruf ist immer von der Form _div( a, b ).
Als Rückgabewert liefert uns die Funktion den ganzzahligen Quotienten von a und b.
Wir führen wieder die gleichen Berechnungen wie oben durch, nur jetzt mit Hilfe
der Funktion _div:
_div(10, 3)
_div(10, 4)
_div(10, 5)
Bei kryptographischen Verschlüsselungsverfahren wie RSA ist das modulare
Potenzieren essentiell (d.h. wir müssen "a hoch b mod m" berechnen können).
Es sollte nicht nur möglich sein, sondern es sollte möglichst effizient durchgeführt
werden können. Die Funktion powermod kann dazu in MuPAD verwendet werden.
Die Funktion powermod erhält stets drei Argumente:
1. Argument: Eine ganze Zahl b (die Basis, die potenziert werden soll)
2. Argument: Eine ganze Zahl e (der Exponent, mit dem die Basis potenziert wird)
3. Argument: Eine ganze Zahl m (der Modul, bezüglich dem reduziert wird, d.h.
die Zahl bezüglich der "modulo" gerechnet
wird)
Ein Aufruf der Funktion ist immer von der Form powermod( a, b, m ). Er berechnet
als Rückgabewert.
Dass man mit dieser Funktion auch sehr große Zahlen sehr schnell potenzieren kann,
zeigen auch einige der folgenden Beispiele:
powermod(2, 3, 8)
powermod(2, 3, 9)
powermod(1232355, 3252174, 3858683262)
powermod(3483478458, 237237884545, 21821821895)
________________________________________________________________________________
Aufgaben:
1. Berechnen Sie:
(a) 234 mod 23, 234 div 23, _mod(234, 23), _div(234, 23)
(b) 684 mod 34, 684 div 34, _mod(684, 34), _div(684, 34)
2. Berechnen Sie:
(a) 23563563^436747745 mod 23552352353
(b) 25353528834^34743743 mod 2100000000000
_______________________________________________________________________________
Anmerkungen:
1. Weitere Anregungen finden Sie in der Buchreihe Mathematik 1 x anders. In dieser Reihe
wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gelöst. Die
Bücher können unter www.schule.mupad.de/literatur kostenfrei kopiert werden.
_______________________________________________________________________________