\mnb150ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fswiss\fprq2 Arial;}{\f4\froman\fprq2 Times New Roman;}{\f5\fmodern\fprq1 Courier New;}{\f6\fswiss\fprq2 Helvetica;}}
{\colortbl\red0\green0\blue0;\red0\green0\blue255;\red0\green128\blue0;\red255\green0\blue0;\red0\green0\blue128;\red255\green255\blue255;}
\deflang1031\pard\ri4\plain\f5\fs20\cf0\b ________________________________________________________________________________
\par
\par \plain\f5\fs20\cf0 Inhalt....: Modulares Rechnen
\par Kategorie.: Grundkurs
\par Mathematik: Zahlentheorie, Kryptographie
\par MuPAD.....: 3.0.0
\par Datum.....: 2004-03-31
\par Autoren...: Kai Gehrs
\par Funktionen: mod, _mod, div, _div, powermod
\par \plain\f5\fs20\cf0\b ________________________________________________________________________________
\par \plain\f3\fs36\cf0\b
\par \plain\f3\fs40\cf0\b Modulares Rechnen
\par
\par \plain\f3\fs24\cf2 Dieses Arbeitsblatt ist Bestandteil des \plain\f3\fs24\cf2\b MuPAD Grundkurses\plain\f3\fs24\cf2 .\plain\f4\fs24
\par
\par \plain\f3\fs28 Das modulare Rechnen wird insbesondere in kryptographischen Anwendungen
\par st\'e4ndig ben\'f6tigt. Aus diesem Grund sollen hier die wichtigsten Funktionen "div",
\par "mod" und "powermod" vorgestellt werden.
\par
\par Mit Hilfe der MuPAD Funktion "mod" l\'e4sst sich der nichtnegative Rest bei der
\par Division zweier ganzer Zahlen berechnen. Die Funktion "mod" kann so verwen-
\par det werden, wie man es von den \'fcblichen Operatoren +, -, * und / in MuPAD
\par gewohnt ist, d.h. die Funktion erh\'e4lt nicht wirklich Argumente als Eingabe. Ein
\par Aufruf der Form "a mod b" f\'fcr ganze Zahlen a und b berechnet als R\'fcckgabe-
\par wert den nichtnegativen Rest bei ganzzahliger Division von a durch b.
\par
\par Die Handhabung der Funktion ist also denkbar einfach. Wir betrachten einige
\par Beispiele und machen jeweils auch die Probe:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 mod 3
\par \pard\ri4\plain\f3\fs28 Denn es gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 = 3 * 3 + 1
\par \pard\li600\ri1\fi-300\plain\f5\fs28\cf3
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 mod 4
\par \pard\ri4\plain\f3\fs28 Denn es gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 = 2 * 4 + 2
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 mod 5
\par \pard\ri4\plain\f3\fs28 Denn es gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 = 2 * 5 + 0
\par \pard\ri4\plain\f3\fs28 Zus\'e4tzlich ist es m\'f6glich, die Funktion "_mod" zu verwenden. Sie ist sozusagen
\par die "funktionale Variante" zu dem Operator "mod".
\par
\par Die Funktion "_mod" erh\'e4lt stets zwei Argumente: Eine ganze Zahl a und eine
\par ganze Zahl b, d.h. also ein Aufruf ist immer von der Form "_mod( a, b )". Als
\par R\'fcckgabewert liefert uns die Funktion "_mod" ebenfalls den nichtnegativen
\par ganzzahligen Rest bei Division von a durch b. Wir berechnen die gleichen
\par Reste wie oben nun mit Hilfe der Funktion "_mod":
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}_mod(10, 3)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}_mod(10, 4)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}_mod(10, 5)
\par \pard\ri4\plain\f3\fs28 Wenn wir den Rest bei ganzzahliger Division zweier Zahlen berechnen k\'f6nnen,
\par so m\'f6chten wir unter Umst\'e4nden auch den Quotienten der beiden Zahlen be-
\par stimmen. Diesem Zweck dient der Operator "div" bzw. die Funktion "_div".
\par
\par Die Verwendung ist ganz analog zu der von "mod" bzw. "_mod".
\par
\par Die Funktion "div" kann so verwendet werden, wie man es von den \'fcblichen
\par Operatoren +, -, * und / in MuPAD gewohnt ist, d.h. die Funktion erh\'e4lt nicht
\par wirklich Argumente als Eingabe.
\par
\par Ein Aufruf der Form "a div b" f\'fcr ganze Zahlen a und b berechnet als R\'fcck-
\par gabewert den ganzzahligen Quotienten von a und b.
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 div 3
\par \pard\ri4\plain\f3\fs28\cf0 Denn es gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 = 3 * 3 + 1
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 div 4
\par \pard\ri4\plain\f3\fs28\cf0 Denn es gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 = 2 * 4 + 2
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 div 5
\par \pard\ri4\plain\f3\fs28\cf0 Denn es gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}10 = 2 * 5 + 0
\par \pard\ri4\plain\f3\fs28 Analog beschreiben wir die Funktion "_div": Die Funktion "_div" erh\'e4lt stets
\par zwei Argumente: Eine ganze Zahl a und eine ganze Zahl b, d.h. also ein
\par Aufruf ist immer von der Form "_div( a, b )". Als R\'fcckgabewert liefert uns die
\par Funktion den ganzzahligen Quotienten von a und b. Wir f\'fchren wieder die
\par gleichen Berechnungen wie oben durch, nur jetzt mit Hilfe der Funktion "_div":
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}_div(10, 3)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}_div(10, 4)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}_div(10, 5)
\par \pard\ri4\plain\f3\fs28 Bei kryptographischen Verschl\'fcsselungsverfahren wie RSA ist das modulare
\par Potenzieren essentiell (d.h. wir m\'fcssen "a hoch b mod m" berechnen k\'f6nnen).
\par Es sollte nicht nur m\'f6glich sein, sondern es sollte m\'f6glichst effizient durchge-
\par f\'fchrt werden k\'f6nnen. Die Funktion "powermod" kann dazu in MuPAD verwendet
\par werden. Die Funktion "powermod" erh\'e4lt stets drei Argumente: Eine ganze Zahl
\par b (die Basis, die potenziert werden soll), eine ganze Zahl e (der Exponent, mit
\par dem die Basis potenziert wird) und schlie\'dflich eine Zahl m (der Modul, bez\'fcglich
\par dem reduziert wird, d.h. die Zahl bez\'fcglich der "modulo" gerechnet wird). Ein
\par Aufruf der Funktion ist immer von der Form "powermod( a, b, m )". Er berechnet
\par "a hoch b mod m" als R\'fcckgabewert.
\par
\par Dass man mit dieser Funktion auch sehr gro\'dfe Zahlen sehr schnell potenzieren
\par kann, zeigen auch einige der folgenden Beispiele:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}powermod(2, 3, 8)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}powermod(2, 3, 9)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}powermod(1232355, 3252174, 3858683262)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf3 {\pntext\f1\'b7\tab}powermod(3483478458, 237237884545, 21821821895)
\par \pard\ri4\plain\f5\fs20\cf0\b ________________________________________________________________________________
\par \plain\f3\fs22\cf1\b
\par \plain\f3\fs22\cf4\b \'dcbungen:
\par 1.\plain\f3\fs22\cf4 Berechnen Sie: 234 mod 23, 234 div 23, _mod(234, 23), _div(234, 23), 684 mod 34, 684 div 34,
\par \plain\f3\fs22\cf5 __\plain\f3\fs22\cf4 _mod(684, 34), _div(684, 34).
\par \plain\f3\fs22\cf5 __
\par __\plain\f3\fs22\cf4 Bestimmen Sie ferner mit Hilfe der Funktion "powermod": 23563563^436747745 mod 23552352353
\par \plain\f3\fs22\cf5 __\plain\f3\fs22\cf4 und 25353528834^34743743 mod 2100000000000.
\par \plain\f5\fs20\cf0\b _______________________________________________________________________________
\par \plain\f3\fs22\cf0
\par \plain\f3\fs22\cf2\b Anmerkungen:\plain\f3\fs22\cf2
\par \plain\f3\fs20\cf2\b 1\plain\f3\fs20\cf2 . Weitere Anregungen finden Sie in der Buchreihe \plain\f3\fs20\cf3 Mathematik 1 x anders\plain\f3\fs20\cf2 . In dieser Reihe
\par wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gel\'f6st. Die
\par B\'fccher k\'f6nnen unter \plain\f6\fs20\cf1 www.schule.mupad.de/literatur\plain\f3\fs20\cf2 kostenfrei kopiert werden.
\par \plain\f3\fs20\cf1
\par \plain\f5\fs20\cf0\b _______________________________________________________________________________
\par \plain\f5\fs28\cf3
\par
\par }