________________________________________________________________________________
Inhalt....: Modulares Rechnen
Kategorie.: Grundkurs
Mathematik: Zahlentheorie, Kryptographie
MuPAD.....: 3.0.0
Datum.....: 2004-03-31
Autoren...: Kai Gehrs <acrowley@mupad.de>
Funktionen: mod, _mod, div, _div, powermod
________________________________________________________________________________
Modulares Rechnen
Dieses Arbeitsblatt ist Bestandteil des MuPAD Grundkurses.
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ässt sich der nichtnegative Rest bei der
Division zweier ganzer Zahlen berechnen. Die Funktion "mod" kann so verwen-
det 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ückgabe-
wert 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 es 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: Eine ganze Zahl a und 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 be-
stimmen. 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ück-
gabewert 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: Eine ganze Zahl a und 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 durchge-
führt werden können. Die Funktion "powermod" kann dazu in MuPAD verwendet
werden. Die Funktion "powermod" erhält stets drei Argumente: Eine ganze Zahl
b (die Basis, die potenziert werden soll), eine ganze Zahl e (der Exponent, mit
dem die Basis potenziert wird) und schließlich eine 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
"a hoch b mod m" 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)
________________________________________________________________________________
Übungen:
1. Berechnen Sie: 234 mod 23, 234 div 23, _mod(234, 23), _div(234, 23), 684 mod 34, 684 div 34,
___mod(684, 34), _div(684, 34).
__
__Bestimmen Sie ferner mit Hilfe der Funktion "powermod": 23563563^436747745 mod 23552352353
__und 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.
_______________________________________________________________________________