\mnb150ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fswiss\fprq2 Arial;}{\f4\fmodern\fprq1 Courier New;}{\f5\fswiss\fprq2 Helvetica;}}
{\colortbl\red0\green0\blue0;\red0\green0\blue255;\red255\green0\blue0;\red0\green128\blue0;}
\deflang1031\pard\ri4\plain\f4\fs20\cf0\b ________________________________________________________________________________
\par
\par \plain\f4\fs20\cf0 Inhalt....: Modulares Rechnen
\par Kategorie.: Handwerkskasten
\par Mathematik: Zahlentheorie, Kryptographie
\par MuPAD.....: 3.0.0
\par Datum.....: 2002-08-14
\par Autoren...: Kai Gehrs
\par Funktionen: div, mod, powermod
\par \plain\f4\fs20\cf0\b ________________________________________________________________________________
\par \plain\f3\fs36\cf0\b
\par \plain\f3\fs40\cf0\b Elementare MuPAD-Funktionen:
\par Modulares Rechnen\plain\f3\fs24\cf3
\par
\par Das modulare Rechnen wird insbesondere in kryptographischen Anwendungen st\'e4ndig ben\'f6tigt.
\par Aus diesem Grund sollen hier die wichtigsten Funktionen 'div', 'mod' und 'powermod' vorgestellt
\par werden.
\par \plain\f3\fs28\cf0
\par \plain\f3\fs28 Mit Hilfe der MuPAD Funktion \plain\f3\fs28\cf2 mod\plain\f3\fs28 l\'e4\'dft sich der nichtnegative Rest bei der
\par Division zweier ganzer Zahlen berechnen.
\par
\par Die Funktion \plain\f3\fs28\cf2 mod\plain\f3\fs28\cf0 kann so verwendet werden, wie man es von den \'fcblichen
\par Operatoren \plain\f3\fs28\cf2 +\plain\f3\fs28\cf0 ,\plain\f3\fs28\cf2 -\plain\f3\fs28\cf0 ,\plain\f3\fs28\cf2 *\plain\f3\fs28\cf0 und \plain\f3\fs28\cf2 /\plain\f3\fs28 in MuPAD gewohnt ist, d.h. die Funktion erh\'e4lt nicht
\par wirklich Argumente als Eingabe.
\par
\par Ein Aufruf der Form \plain\f3\fs28\cf3 a\plain\f3\fs28\cf2 mod \plain\f3\fs28\cf3 b\plain\f3\fs28 f\'fcr ganze Zahlen \plain\f3\fs28\cf3 a\plain\f3\fs28 und \plain\f3\fs28\cf3 b\plain\f3\fs28 berechnet als \plain\f3\fs28\cf1 R\'fcck-
\par gabewert \plain\f3\fs28 den \plain\f3\fs28\cf1 nichtnegativen Rest\plain\f3\fs28 bei ganzzahliger Division \plain\f3\fs28\cf0 von \plain\f3\fs28\cf3 a\plain\f3\fs28\cf0 durch \plain\f3\fs28\cf3 b\plain\f3\fs28\cf0 .
\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\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 mod 3
\par \pard\ri4\plain\f3\fs28\cf0
\par Denn es gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 = 3 * 3 + 1
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 mod 4
\par \pard\ri4\plain\f3\fs28\cf0
\par Denn es gilt:
\par \plain\f4\fs28\cf2
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 = 2 * 4 + 2
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 mod 5
\par \pard\ri4\plain\f3\fs28\cf0
\par Denn gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 = 2 * 5 + 0
\par \pard\ri4\plain\f3\fs28\cf0
\par Zus\'e4tzlich ist es m\'f6glich, die Funktion \plain\f3\fs28\cf2 _mod\plain\f3\fs28\cf0 zu verwenden. Sie ist sozusagen
\par die "funktionale Variante" zu dem "Operator" \plain\f3\fs28\cf2 mod\plain\f3\fs28\cf0 .
\par
\par \plain\f3\fs28 Die Funktion \plain\f3\fs28\cf2 _mod\plain\f3\fs28 erh\'e4lt stets \plain\f3\fs28\cf3 zwei Argumente\plain\f3\fs28 :
\par
\par \plain\f3\fs28\cf2 1. Argument:\plain\f3\fs28 Eine ganze Zahl \plain\f3\fs28\cf3 a\plain\f3\fs28
\par
\par \plain\f3\fs28\cf2 2. Argument:\plain\f3\fs28 Eine ganze Zahl \plain\f3\fs28\cf3 b\plain\f3\fs28
\par
\par d.h. also ein Aufruf ist immer von der Form \plain\f3\fs28\cf2 _mod( \plain\f3\fs28\cf3 a, b\plain\f3\fs28\cf2 )\plain\f3\fs28\cf0 .
\par
\par Als \plain\f3\fs28\cf1 R\'fcckgabewert\plain\f3\fs28\cf0 liefert uns die Funktion \plain\f3\fs28\cf2 _mod\plain\f3\fs28\cf0 ebenfalls den \plain\f3\fs28\cf1 nichtnegativen
\par ganzzahligen Rest\plain\f3\fs28\cf0 bei Division von \plain\f3\fs28\cf3 a\plain\f3\fs28\cf0 durch \plain\f3\fs28\cf3 b\plain\f3\fs28\cf0 .
\par
\par Wir berechnen die gleichen Reste wie oben nun mit Hilfe der Funktion \plain\f3\fs28\cf2 _mod\plain\f3\fs28\cf0 :
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}_mod(10, 3)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}_mod(10, 4)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}_mod(10, 5)
\par \pard\ri4\plain\f3\fs28\cf0
\par 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
\par bestimmen. Diesem Zweck dient der Operator \plain\f3\fs28\cf2 div\plain\f3\fs28\cf0 bzw. die Funktion \plain\f3\fs28\cf2 _div\plain\f3\fs28\cf0 .
\par
\par Die Verwendung ist ganz analog zu der von \plain\f3\fs28\cf2 mod\plain\f3\fs28\cf0 bzw. \plain\f3\fs28\cf2 _mod\plain\f3\fs28\cf0 .
\par
\par \plain\f3\fs28 Die Funktion \plain\f3\fs28\cf2 div\plain\f3\fs28\cf0 kann so verwendet werden, wie man es von den \'fcblichen
\par Operatoren \plain\f3\fs28\cf2 +\plain\f3\fs28\cf0 ,\plain\f3\fs28\cf2 -\plain\f3\fs28\cf0 ,\plain\f3\fs28\cf2 *\plain\f3\fs28\cf0 und \plain\f3\fs28\cf2 /\plain\f3\fs28 in MuPAD gewohnt ist, d.h. die Funktion erh\'e4lt nicht
\par wirklich Argumente als Eingabe.
\par
\par Ein Aufruf der Form \plain\f3\fs28\cf3 a\plain\f3\fs28\cf2 div \plain\f3\fs28\cf3 b\plain\f3\fs28 f\'fcr ganze Zahlen \plain\f3\fs28\cf3 a\plain\f3\fs28 und \plain\f3\fs28\cf3 b\plain\f3\fs28 berechnet als \plain\f3\fs28\cf1 R\'fcckgabewert \plain\f3\fs28
\par den \plain\f3\fs28\cf1 ganzzahligen Quotienten \plain\f3\fs28\cf0 von \plain\f3\fs28\cf3 a\plain\f3\fs28\cf0 und \plain\f3\fs28\cf3 b\plain\f3\fs28\cf0 .
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 div 3
\par \pard\ri4\plain\f3\fs28\cf0
\par Denn es gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 = 3 * 3 + 1
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 div 4
\par \pard\ri4\plain\f3\fs28\cf0
\par Denn es gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 = 2 * 4 + 2
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 div 5
\par \pard\ri4\plain\f3\fs28\cf0
\par Denn es gilt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}10 = 2 * 5 + 0
\par \pard\ri4\plain\f3\fs28\cf0
\par Analog beschreiben wir die Funktion \plain\f3\fs28\cf2 _div\plain\f3\fs28\cf0 :
\par
\par \plain\f3\fs28 Die Funktion \plain\f3\fs28\cf2 _div\plain\f3\fs28 erh\'e4lt stets \plain\f3\fs28\cf3 zwei Argumente\plain\f3\fs28 :
\par
\par \plain\f3\fs28\cf2 1. Argument:\plain\f3\fs28 Eine ganze Zahl \plain\f3\fs28\cf3 a\plain\f3\fs28
\par
\par \plain\f3\fs28\cf2 2. Argument:\plain\f3\fs28 Eine ganze Zahl \plain\f3\fs28\cf3 b\plain\f3\fs28
\par
\par d.h. also ein Aufruf ist immer von der Form \plain\f3\fs28\cf2 _div( \plain\f3\fs28\cf3 a, b\plain\f3\fs28\cf2 )\plain\f3\fs28\cf0 .
\par
\par \plain\f3\fs28 Als \plain\f3\fs28\cf1 R\'fcckgabewert \plain\f3\fs28\cf0 liefert uns die Funktion \plain\f3\fs28 den \plain\f3\fs28\cf1 ganzzahligen Quotienten \plain\f3\fs28\cf0 von \plain\f3\fs28\cf3 a\plain\f3\fs28\cf0 und \plain\f3\fs28\cf3 b\plain\f3\fs28\cf0 .
\par
\par Wir f\'fchren wieder die gleichen Berechnungen wie oben durch, nur jetzt mit Hilfe
\par der Funktion \plain\f3\fs28\cf2 _div\plain\f3\fs28\cf0 :
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}_div(10, 3)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}_div(10, 4)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}_div(10, 5)
\par \pard\ri4\plain\f3\fs28\cf0
\par Bei kryptographischen Verschl\'fcsselungsverfahren wie RSA ist das modulare
\par Potenzieren essentiell (d.h. wir m\'fcssen \plain\f3\fs28\cf0\i "a \plain\f3\fs28\cf0 hoch\plain\f3\fs28\cf0\i b \plain\f3\fs28\cf0 mod \plain\f3\fs28\cf0\i m"\plain\f3\fs28\cf0 berechnen k\'f6nnen).
\par Es sollte nicht nur m\'f6glich sein, sondern es sollte m\'f6glichst effizient durchgef\'fchrt
\par werden k\'f6nnen. Die Funktion \plain\f3\fs28\cf2 powermod\plain\f3\fs28\cf0 kann dazu in MuPAD verwendet werden.
\par
\par \plain\f3\fs28 Die Funktion \plain\f3\fs28\cf2 powermod\plain\f3\fs28 erh\'e4lt stets \plain\f3\fs28\cf3 drei Argumente\plain\f3\fs28 :
\par
\par \plain\f3\fs28\cf2 1. Argument:\plain\f3\fs28 Eine ganze Zahl \plain\f3\fs28\cf3 b (die Basis, die potenziert werden soll)\plain\f3\fs28
\par
\par \plain\f3\fs28\cf2 2. Argument:\plain\f3\fs28 Eine ganze Zahl \plain\f3\fs28\cf3 e (der Exponent, mit dem die Basis potenziert wird)
\par \plain\f3\fs28
\par \plain\f3\fs28\cf2 3. Argument:\plain\f3\fs28 Eine ganze Zahl \plain\f3\fs28\cf3 m (der Modul, bez\'fcglich dem reduziert wird, d.h.
\par die Zahl bez\'fcglich der "modulo" gerechnet
\par wird)\plain\f3\fs28
\par
\par Ein Aufruf der Funktion ist immer von der Form \plain\f3\fs28\cf2 powermod( \plain\f3\fs28\cf3 a, b, m\plain\f3\fs28\cf2 )\plain\f3\fs28\cf0 . Er berechnet
\par
\par {\pict\wmetafile8\picw2142\pich846\picscalex99\picscaley98\picwgoal1222\pichgoal484
010009000003A002000007001C0000000000050000000B0200000000050000000C024E035E0803
0000001E00050000000C0257036C08050000000B0200000000030000001E00050000000C026103
7508050000000B0200000000050000000B0200000000030000001E00050000000C026A03840805
0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000
0C0275038C08050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000030000001E00050000000C027E039C08050000000B0200000000050000000B02
00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E
00050000000C028003A508050000000B0200000000050000000B0200000000050000000B020000
0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005
0000000C028903B508050000000B0200000000050000000B0200000000050000000B0200000000
050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000
00030000001E00050000000C028C03BD08050000000B0200000000050000000B02000000000500
00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005
0000000B0200000000050000000B0200000000030000001E00030000001E00050000000C020302
F404050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200
000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02
00000000050000000B020000000008000000FA0200000000000000000000040000002D0100001C
000000FB0238FF00000000000090010000000107000000417269616C000000330C0AC438E91200
D89FF177E19FF1772020F377310A66FD040000002D010100050000000201010000000500000001
02FFFFFF00050000002E01180000000500000009020000000004000000080100001C000000FB02
E8FE0000000000009001000000010700000054696D6573204E657720526F6D616E00D89FF177E1
9FF1772020F377310A66FD040000002D0102000B00000026060F000C004D617468547970650000
80001C000000FB02E8FE0000000000009001010000010700000054696D6573204E657720526F6D
616E00D89FF177E19FF1772020F377310A66FD040000002D0103001C000000FB023AFF00000000
00009001010000010700000054696D6573204E657720526F6D616E00D89FF177E19FF1772020F3
77310A66FD040000002D010400040000002D010300040000002D0102000500000009020000FF00
040000002D0103000700000021050100620062016400040000002D010400070000002105010065
00D300F000040000002D01020007000000210501006D0062018E0107000000210501006F006201
6802070000002105010064006201F402040000002D01030007000000210501006D006201C60308
000000FA0200000000000000000000040000002D0105001C000000FB021000070000000000BC02
000000000102022253797374656D0000F00B0A4538E91200D89FF177E19FF1772020F377310A66
FD040000002D010600040000002701FFFF04000000F001000004000000F001010004000000F001
020004000000F001030004000000F0010400040000002701FFFF040000002701FFFF0400000027
01FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF04000000
2701FFFF040000002701FFFF030000000000
}\plain\f3\fs28\cf0
\par
\par \plain\f3\fs28 als \plain\f3\fs28\cf1 R\'fcckgabewert\plain\f3\fs28\cf0 .
\par
\par Dass man mit dieser Funktion auch sehr gro\'dfe Zahlen sehr schnell potenzieren kann,
\par zeigen auch einige der folgenden Beispiele:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}powermod(2, 3, 8)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}powermod(2, 3, 9)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}powermod(1232355, 3252174, 3858683262)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}powermod(3483478458, 237237884545, 21821821895)
\par \pard\ri4\plain\f3\fs28\cf0
\par \plain\f4\fs20\cf0\b
\par ________________________________________________________________________________
\par \plain\f3\fs22\cf0
\par \plain\f3\fs22\cf1\b Aufgaben:\plain\f3\fs22\cf1
\par \plain\f3\fs20\cf1\b 1.\plain\f3\fs20\cf1 Berechnen Sie:
\par (a) 234 mod 23, 234 div 23, _mod(234, 23), _div(234, 23)
\par (b) 684 mod 34, 684 div 34, _mod(684, 34), _div(684, 34)\plain\f3\fs20\cf3
\par \plain\f3\fs20\cf1
\par \plain\f3\fs20\cf1\b 2.\plain\f3\fs20\cf1 Berechnen Sie:
\par (a) 23563563^436747745 mod 23552352353
\par (b) 25353528834^34743743 mod 2100000000000
\par \plain\f4\fs20\cf0\b _______________________________________________________________________________
\par \plain\f3\fs22\cf0
\par \plain\f3\fs22\cf3\b Anmerkungen:\plain\f3\fs22\cf3
\par \plain\f3\fs20\cf3\b 1\plain\f3\fs20\cf3 . Weitere Anregungen finden Sie in der Buchreihe \plain\f3\fs20\cf2 Mathematik 1 x anders\plain\f3\fs20\cf3 . In dieser Reihe
\par wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gel\'f6st. Die
\par B\'fccher k\'f6nnen unter \plain\f5\fs20\cf1 www.schule.mupad.de/literatur\plain\f3\fs20\cf3 kostenfrei kopiert werden.
\par \plain\f3\fs20\cf1
\par \plain\f4\fs20\cf0\b _______________________________________________________________________________
\par
\par
\par }