\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;}{\f6\froman\fprq2 Times New Roman;}}
{\colortbl\red0\green0\blue0;\red0\green128\blue0;\red255\green0\blue0;\red0\green0\blue255;\red0\green0\blue128;\red255\green255\blue255;}
\deflang1031\pard\ri4\plain\f4\fs20\cf0\b ________________________________________________________________________________
\par
\par \plain\f4\fs20\cf0 Inhalt....: Primzahlen
\par Kategorie.: Grundkurs
\par Mathematik: Zahlentheorie, Kryptographie
\par MuPAD.....: 3.0.0
\par Datum.....: 2004-03-31
\par Autoren...: Kai Gehrs
\par Funktionen: isprime, ithprime, nextprime, ifactor
\par \plain\f4\fs20\cf0\b ________________________________________________________________________________
\par \plain\f3\fs36\cf0\b
\par \plain\f3\fs40\cf0\b Primzahlen
\par
\par \plain\f3\fs24\cf1 Dieses Arbeitsblatt ist Bestandteil des \plain\f3\fs24\cf1\b MuPAD Grundkurses\plain\f3\fs24\cf1 .\plain\f6\fs24
\par
\par \plain\f3\fs28 Primzahlen sind seit jeher ein interessanter Bereich der Zahlentheorie. Hier
\par lernen wir, wie wir mit MuPAD Zahlen auf Primheit testen k\'f6nnen, wie wir die
\par i-te Primzahl bestimmen k\'f6nnen (i eine positive ganze Zahl) und auch wie wir
\par die n\'e4chst gr\'f6\'dfere Primzahl zu einer gegebenen Zahl mit MuPAD erhalten.
\par In diesem Zusammenhang werden wir auch die Funktion "ifactor" zur Faktori-
\par sierung kennenlernen.
\par
\par Um zu testen, ob eine Zahl eine Primzahl ist, stellt MuPAD die Funktion "isprime"
\par zur Verf\'fcgung. Die Funktion "isprime" erh\'e4lt stets ein Argument: Eine positive
\par ganze Zahl a, d.h. also ein Aufruf ist immer von der Form "isprime( a )". Als R\'fcck-
\par gabewert liefert uns die Funktion "isprime" den Wert TRUE, falls a eine Primzahl
\par ist, und FALSE, falls a 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\f4\fs28\cf2 {\pntext\f1\'b7\tab}isprime(11)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}isprime(12)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}isprime(167)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}isprime(169)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}isprime(2^(2^4) + 1)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}isprime(2^(2^5) + 1)
\par \pard\ri4\plain\f3\fs28 Haben wir eine Zahl darauf getestet, ob es sich um eine Primzahl handelt, und
\par haben wir festgestellt, dass die betrachtete Zahl nicht prim ist (d.h. keine Prim-
\par zahl ist), so ist es unter Umst\'e4nden von Interesse, die n\'e4chst gr\'f6\'dfere Primzahl
\par zu finden. Dies ist immer dann interessant, wenn man eine Primzahl von einer
\par bestimmten Gr\'f6\'dfenordnung sucht - dann ist das kanonische Vorgehen einfach
\par eine Zahl der entsprechenden Gr\'f6\'dfenordnung zu w\'e4hlen und die n\'e4chst gr\'f6\'dfere
\par Primzahl zu bestimmen.
\par
\par Die Funktion, die dies erledigt, ist die Funktion "nextprime": Sie erh\'e4lt stets ein
\par Argument: Eine positive ganze Zahl a, d.h. also ein Aufruf ist immer von der
\par Form "nextprime( a )". Als R\'fcckgabewert liefert uns die Funktion nextprime die
\par kleinste Primzahl, die gr\'f6\'dfer oder gleich a ist. In dem Fall, dass a eine Primzahl
\par ist, liefert die Funktion also die Zahl a selbst zur\'fcck.
\par
\par Auch zu dieser Funktion einige Beispiele:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}nextprime(4)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}nextprime(7)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}nextprime(7+1)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}nextprime(65537)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}nextprime(7237832782188956092356216)
\par \pard\ri4\plain\f3\fs28 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 "ithprime" finden. Die Funktion "ithprime" erh\'e4lt stets ein
\par Argument: Eine positive ganze Zahl i, d.h. also ein Aufruf ist immer von der Form
\par "ithprime( i )". Als R\'fcckgabewert liefert uns die Funktion ithprime die i-te Primzahl.
\par
\par Wir bestimmen die 1000. Primzahl, die 5000. Primzahl und die 123456. Primzahl:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}ithprime(1000)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}ithprime(10000)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}ithprime(123456)
\par \pard\ri4\plain\f3\fs28 Die erste Funktion, die wir in diesem Abschnitt kennengelernt haben, war die
\par Funktion "isprime" 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 handelt,
\par so muss die betrachtete Zahl zusammengesetzt sein, d.h. sie ist in ein Produkt
\par von Primzahlpotenzen zerlegbar. Man spricht davon, dass sich die Zahl "faktori-
\par sieren" l\'e4sst.
\par
\par Die Faktorisierung einer ganzen Zahl kann in MuPAD mittels der Funktion "ifactor"
\par berechnet werden. Leider sind Faktorisierungsalgorithmen nicht ann\'e4hernd so
\par effizient, wie zum Beispiel einige der Algorithmen, die testen ob eine gegebene
\par Zahl eine Primzahl ist.
\par
\par Daher: Bei der Berechnung der Faktorisierung gro\'dfer Zahlen ben\'f6tigt man auch
\par in MuPAD Geduld (auf dieser "Ineffizienz" von Faktorisierungsalgorithmen beruht
\par \'fcbrigens entscheidend die Sicherheit vieler Verfahren in der Kryptographie - so
\par z.B. auch die Sicherheit von RSA).
\par
\par Die Funktion ifactor erh\'e4lt stets ein Argument: Eine positive ganze Zahl a, d.h.
\par also ein Aufruf ist immer von der Form "ifactor( a )". Als R\'fcckgabewert liefert uns
\par die Funktion ifactor die Faktorisierung der Zahl a, falls a zusammengesetzt (also
\par kein Primzahl) ist, und a, falls a eine Primzahl ist.
\par
\par Nun zu einigen Beispielen:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}ifactor(64)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}ifactor(124)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}ifactor(15254727)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}ifactor(74757235275979)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}ifactor(33333333)
\par \pard\ri4\plain\f3\fs28 Anstelle von "ifactor" kann man auch die Funktion "factor" aufrufen. Dann muss
\par allerdings das System intern erst feststellen, dass es sich bei den Eingaben um
\par ganze Zahlen handelt (denn mit "factor" kann man z.B. auch Polynome faktori-
\par sieren). Wenn man also wirklich effizient und schnell gro\'dfe ganze Zahlen faktori-
\par sieren m\'f6chte, so sollte man die Funktion "ifactor" verwenden, um nicht unn\'f6tig
\par Rechenzeit f\'fcr sogenannte interne Typ-\'dcberpr\'fcfungen zu verschwenden.
\par
\par \plain\f4\fs20\cf0\b ________________________________________________________________________________
\par \plain\f3\fs22\cf3\b
\par \plain\f3\fs22\cf4\b \'dcbungen:
\par 1.\plain\f3\fs22\cf4 Ist 32765487239865 eine Primzahl? Wenn nein, so berechnen Sie die Primfaktorzerlegung dieses
\par \plain\f3\fs22\cf5 __\plain\f3\fs22\cf4 Zahl. Welche Primzahl ist die n\'e4chste, die auf 32765487239865 folgt?
\par \plain\f4\fs20\cf0\b _______________________________________________________________________________
\par \plain\f3\fs22\cf0
\par \plain\f3\fs22\cf1\b Anmerkungen:\plain\f3\fs22\cf1
\par \plain\f3\fs20\cf1\b 1\plain\f3\fs20\cf1 . Weitere Anregungen finden Sie in der Buchreihe \plain\f3\fs20\cf2 Mathematik 1 x anders\plain\f3\fs20\cf1 . In dieser Reihe
\par wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gel\'f6st. Die
\par B\'fccher k\'f6nnen unter \plain\f5\fs20\cf3 www.schule.mupad.de/literatur\plain\f3\fs20\cf1 kostenfrei kopiert werden.
\par \plain\f3\fs20\cf3
\par \plain\f4\fs20\cf0\b _______________________________________________________________________________
\par \plain\f4\fs28\cf2
\par
\par }