\mnb150ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fmodern\fprq1 Courier New;}{\f4\fswiss\fprq2 Arial;}{\f5\fswiss\fprq2 Helvetica;}}
{\colortbl\red0\green0\blue0;\red255\green0\blue0;\red0\green0\blue255;\red0\green128\blue0;}
\deflang1031\pard\ri4\plain\f3\fs20\cf0\b ________________________________________________________________________________
\par
\par \plain\f3\fs20\cf0 Inhalt....: Primzahlen in MuPAD
\par Kategorie.: Handwerkskasten
\par Mathematik: Zahlentheorie, Kryptographie
\par MuPAD.....: 3.0.0
\par Datum.....: 2002-08-14
\par Autoren...: Kai Gehrs
\par Funktionen: isprime, nextprime, ithprime, ifactor, factor
\par \plain\f3\fs20\cf0\b ________________________________________________________________________________
\par \plain\f4\fs36\cf0\b
\par \plain\f4\fs40\cf0\b Elementare MuPAD-Funktionen:
\par Primzahlen in MuPAD\plain\f4\fs24\cf3
\par
\par Primzahlen sind seit jeher ein interessanter Bereich der Zahlentheorie. Hier lernen wir, wie wir mit
\par MuPAD Zahlen auf Primheit testen k\'f6nnen, wie wir die i-te Primzahl bestimmen k\'f6nnen (i eine
\par positive ganze Zahl) und auch wie wir die n\'e4chst gr\'f6\'dfere Primzahl zu einer gegebenen Zahl mit
\par MuPAD erhalten. In diesem Zusammenhang werden wir auch die Funktion 'ifactor' zur Faktorisierung
\par kennenlernen.
\par \plain\f4\fs28\cf0
\par \plain\f4\fs28 Um zu testen, ob eine Zahl eine Primzahl ist, stellt MuPAD die Funktion \plain\f4\fs28\cf1 isprime\plain\f4\fs28
\par zur Verf\'fcgung.
\par
\par Die Funktion \plain\f4\fs28\cf1 isprime\plain\f4\fs28 erh\'e4lt stets \plain\f4\fs28\cf3 ein Argument\plain\f4\fs28 :
\par
\par \plain\f4\fs28\cf1 1. Argument:\plain\f4\fs28 Eine positive ganze Zahl \plain\f4\fs28\cf3 a\plain\f4\fs28
\par
\par d.h. also ein Aufruf ist immer von der Form \plain\f4\fs28\cf1 isprime( \plain\f4\fs28\cf3 a\plain\f4\fs28\cf1 )\plain\f4\fs28\cf0 .
\par
\par Als \plain\f4\fs28\cf2 R\'fcckgabewert\plain\f4\fs28\cf0 liefert uns die Funktion \plain\f4\fs28\cf1 isprime\plain\f4\fs28\cf0 den Wert \plain\f4\fs28\cf2 TRUE\plain\f4\fs28\cf0 , falls \plain\f4\fs28\cf3 a\plain\f4\fs28\cf0 eine
\par Primzahl ist, und \plain\f4\fs28\cf2 FALSE\plain\f4\fs28\cf0 , falls \plain\f4\fs28\cf3 a\plain\f4\fs28\cf0 eine zusammengesetzte Zahl ist.
\par
\par Einige kleine Beispiele verdeutlichen wie immer den Umgang mit dieser neuen
\par Funktion:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}isprime(11)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}isprime(12)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}isprime(167)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}isprime(169)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}isprime(2^(2^4) + 1)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}isprime(2^(2^5) + 1)
\par \pard\ri4\plain\f4\fs28\cf0
\par Haben wir eine Zahl darauf getestet, ob es sich um eine Primzahl handelt, und
\par haben wir festgestellt, dass die betrachtete nicht prim ist (d.h. keine Primzahl ist),
\par so ist es unter Umst\'e4nden von Interesse, die n\'e4chst gr\'f6\'dfere Primzahl zu finden.
\par Dies ist immer dann interessant, wenn man eine Primzahl von einer bestimmten
\par Gr\'f6\'dfenordnung sucht - dann ist das kanonische Vorgehen einfach eine Zahl der
\par entsprechenden Gr\'f6\'dfenordnung zu w\'e4hlen und die n\'e4chst gr\'f6\'dfere Primzahl zu
\par bestimmen.
\par
\par Die Funktion, die dies erledigt, ist die Funktion \plain\f4\fs28\cf1 nextprime\plain\f4\fs28\cf0 :
\par
\par \plain\f4\fs28 Die Funktion \plain\f4\fs28\cf1 nextprime\plain\f4\fs28 erh\'e4lt stets \plain\f4\fs28\cf3 ein Argument\plain\f4\fs28 :
\par
\par \plain\f4\fs28\cf1 1. Argument:\plain\f4\fs28 Eine positive ganze Zahl \plain\f4\fs28\cf3 a\plain\f4\fs28
\par
\par d.h. also ein Aufruf ist immer von der Form \plain\f4\fs28\cf1 nextprime( \plain\f4\fs28\cf3 a\plain\f4\fs28\cf1 )\plain\f4\fs28\cf0 .
\par
\par Als \plain\f4\fs28\cf2 R\'fcckgabewert\plain\f4\fs28\cf0 liefert uns die Funktion \plain\f4\fs28\cf1 nextprime\plain\f4\fs28\cf0 die \plain\f4\fs28\cf2 kleinste Primzahl, die
\par gr\'f6\'dfer oder gleich\plain\f4\fs28\cf0 \plain\f4\fs28\cf3 a\plain\f4\fs28\cf0 ist. In dem Fall, dass \plain\f4\fs28\cf3 a \plain\f4\fs28\cf0 eine Primzahl ist, liefert die Funktion
\par also \plain\f4\fs28\cf2 die Zahl\plain\f4\fs28\cf0 \plain\f4\fs28\cf3 a \plain\f4\fs28\cf2 selbst\plain\f4\fs28\cf0 zur\'fcck.
\par
\par Auch zu dieser Funktion einige Beispiele:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}nextprime(4)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}nextprime(7)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}nextprime(7+1)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}nextprime(65537)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}nextprime(7237832782188956092356216)
\par \pard\ri4\plain\f4\fs28\cf0
\par Wollen wir explizit die i-te Primzahl bestimmen (dabei denken wir uns nat\'fcrlich
\par alle Primzahlen der Gr\'f6\'dfe nach aufsteigend angeordnet), so k\'f6nnen wir diese
\par mit Hilfe der Funktion \plain\f4\fs28\cf1 ithprime\plain\f4\fs28\cf0 finden:
\par
\par \plain\f4\fs28 Die Funktion \plain\f4\fs28\cf1 ithprime\plain\f4\fs28 erh\'e4lt stets \plain\f4\fs28\cf3 ein Argument\plain\f4\fs28 :
\par
\par \plain\f4\fs28\cf1 1. Argument:\plain\f4\fs28 Eine positive ganze Zahl \plain\f4\fs28\cf3 i\plain\f4\fs28
\par
\par d.h. also ein Aufruf ist immer von der Form \plain\f4\fs28\cf1 ithprime( \plain\f4\fs28\cf3 i\plain\f4\fs28\cf1 )\plain\f4\fs28\cf0 .
\par
\par Als \plain\f4\fs28\cf2 R\'fcckgabewert\plain\f4\fs28\cf0 liefert uns die Funktion \plain\f4\fs28\cf1 ithprime\plain\f4\fs28\cf0 die \plain\f4\fs28\cf2 i-te Primzahl\plain\f4\fs28\cf0 .
\par
\par Wir bestimmen die 1000. Primzahl, die 5000. Primzahl und die
\par 123456. Primzahl:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}ithprime(1000)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}ithprime(10000)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}ithprime(123456)
\par \pard\ri4\plain\f4\fs28\cf0
\par Die erste Funktion, die wir in diesem Notebook kennengelernt haben, war
\par die Funktion \plain\f4\fs28\cf1 isprime\plain\f4\fs28\cf0 zum Test, ob eine Zahl eine Primzahl ist oder nicht.
\par
\par Haben wir von einer Zahl festgestellt, dass es sich nicht um eine Primzahl
\par handelt, so muss die betrachtete Zahl zusammengesetzt sein, d.h. sie ist
\par in ein Produkt von Primzahlpotenzen zerlegbar. Man spricht davon, dass
\par sich die Zahl "faktorisieren" l\'e4\'dft.
\par
\par Die Faktorisierung einer ganzen Zahl kann in MuPAD mittels der Funktion
\par \plain\f4\fs28\cf1 ifactor\plain\f4\fs28\cf0 berechnet werden. Leider sind Faktorisierungsalgorithmen nicht
\par ann\'e4hernd so effizient, wie zum Beispiel einige der Algorithmen, die testen
\par ob eine gegebene Zahl eine Primzahl ist.
\par
\par Daher: Bei der Berechnung der Faktorisierung gro\'dfer Zahlen ben\'f6tigt man
\par auch in MuPAD Geduld (auf dieser "Ineffizienz" von Faktorisierungsalgorithmen
\par beruht \'fcbrigens entscheidend die Sicherheit vieler Verfahren in der Krypto-
\par graphie - so z.B. auch die Sicherheit von RSA).
\par
\par \plain\f4\fs28 Die Funktion \plain\f4\fs28\cf1 ifactor\plain\f4\fs28\cf0 \plain\f4\fs28 erh\'e4lt stets \plain\f4\fs28\cf3 ein Argument\plain\f4\fs28 :
\par
\par \plain\f4\fs28\cf1 1. Argument:\plain\f4\fs28 Eine positive ganze Zahl \plain\f4\fs28\cf3 a\plain\f4\fs28
\par
\par d.h. also ein Aufruf ist immer von der Form \plain\f4\fs28\cf1 ifactor\plain\f4\fs28\cf0 \plain\f4\fs28\cf1 ( \plain\f4\fs28\cf3 a\plain\f4\fs28\cf1 )\plain\f4\fs28\cf0 .
\par
\par Als \plain\f4\fs28\cf2 R\'fcckgabewert\plain\f4\fs28\cf0 liefert uns die Funktion \plain\f4\fs28\cf1 ifactor\plain\f4\fs28\cf0 die \plain\f4\fs28\cf2 Faktorisierung der Zahl\plain\f4\fs28\cf0
\par \plain\f4\fs28\cf3 a\plain\f4\fs28\cf0 , falls \plain\f4\fs28\cf3 a\plain\f4\fs28\cf0 zusammengesetzt (also kein Primzahl) ist, und \plain\f4\fs28\cf3 a\plain\f4\fs28\cf0 , falls \plain\f4\fs28\cf3 a\plain\f4\fs28\cf0 eine
\par Primzahl ist.
\par
\par Nun zu einigen Beispielen:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}ifactor(64)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}ifactor(124)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}ifactor(15254727)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}ifactor(74757235275979)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}ifactor(33333333)
\par \pard\ri4\plain\f4\fs28\cf0
\par Anstelle von \plain\f4\fs28\cf1 ifactor\plain\f4\fs28\cf0 kann man auch die Funktion \plain\f4\fs28\cf1 factor\plain\f4\fs28\cf0 aufrufen. Dann mu\'df
\par allerdings das System intern erst feststellen, dass es sich bei den Eingaben
\par um ganze Zahlen handelt (denn mit \plain\f4\fs28\cf1 factor\plain\f4\fs28\cf0 kann man z.B. auch Polynome
\par faktorisieren). Wenn man also wirklich effizient und schnell gro\'dfe ganze
\par Zahlen faktorisieren m\'f6chte, so sollte man die Funktion \plain\f4\fs28\cf1 ifactor\plain\f4\fs28\cf0 verwenden,
\par um nicht unn\'f6tig Rechenzeit f\'fcr sogenannte interne Typ-\'dcberpr\'fcfungen
\par zu verschwenden.
\par \plain\f3\fs20\cf0\b
\par _______________________________________________________________________________
\par \plain\f4\fs22\cf0
\par \plain\f4\fs22\cf3\b Anmerkungen:\plain\f4\fs22\cf3
\par \plain\f4\fs20\cf3\b 1\plain\f4\fs20\cf3 . Weitere Anregungen finden Sie in der Buchreihe \plain\f4\fs20\cf1 Mathematik 1 x anders\plain\f4\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\cf2 www.schule.mupad.de/literatur\plain\f4\fs20\cf3 kostenfrei kopiert werden.
\par \plain\f4\fs20\cf2
\par \plain\f3\fs20\cf0\b _______________________________________________________________________________
\par
\par
\par }