________________________________________________________________________________
Inhalt....: Primzahlen
Kategorie.: Grundkurs
Mathematik: Zahlentheorie, Kryptographie
MuPAD.....: 3.0.0
Datum.....: 2004-03-31
Autoren...: Kai Gehrs <acrowley@mupad.de>
Funktionen: isprime, ithprime, nextprime, ifactor
________________________________________________________________________________
Primzahlen
Dieses Arbeitsblatt ist Bestandteil des MuPAD Grundkurses.
Primzahlen sind seit jeher ein interessanter Bereich der Zahlentheorie. Hier
lernen wir, wie wir mit MuPAD Zahlen auf Primheit testen können, wie wir die
i-te Primzahl bestimmen können (i eine positive ganze Zahl) und auch wie wir
die nächst größere Primzahl zu einer gegebenen Zahl mit MuPAD erhalten.
In diesem Zusammenhang werden wir auch die Funktion "ifactor" zur Faktori-
sierung kennenlernen.
Um zu testen, ob eine Zahl eine Primzahl ist, stellt MuPAD die Funktion "isprime"
zur Verfügung. Die Funktion "isprime" erhält stets ein Argument: Eine positive
ganze Zahl a, d.h. also ein Aufruf ist immer von der Form "isprime( a )". Als Rück-
gabewert liefert uns die Funktion "isprime" den Wert TRUE, falls a eine Primzahl
ist, und FALSE, falls a eine zusammengesetzte Zahl ist.
Einige kleine Beispiele verdeutlichen wie immer den Umgang mit dieser neuen
Funktion:
isprime(11)
isprime(12)
isprime(167)
isprime(169)
isprime(2^(2^4) + 1)
isprime(2^(2^5) + 1)
Haben wir eine Zahl darauf getestet, ob es sich um eine Primzahl handelt, und
haben wir festgestellt, dass die betrachtete Zahl nicht prim ist (d.h. keine Prim-
zahl ist), so ist es unter Umständen von Interesse, die nächst größere Primzahl
zu finden. Dies ist immer dann interessant, wenn man eine Primzahl von einer
bestimmten Größenordnung sucht - dann ist das kanonische Vorgehen einfach
eine Zahl der entsprechenden Größenordnung zu wählen und die nächst größere
Primzahl zu bestimmen.
Die Funktion, die dies erledigt, ist die Funktion "nextprime": Sie erhält stets ein
Argument: Eine positive ganze Zahl a, d.h. also ein Aufruf ist immer von der
Form "nextprime( a )". Als Rückgabewert liefert uns die Funktion nextprime die
kleinste Primzahl, die größer oder gleich a ist. In dem Fall, dass a eine Primzahl
ist, liefert die Funktion also die Zahl a selbst zurück.
Auch zu dieser Funktion einige Beispiele:
nextprime(4)
nextprime(7)
nextprime(7+1)
nextprime(65537)
nextprime(7237832782188956092356216)
Wollen wir explizit die i-te Primzahl bestimmen (dabei denken wir uns natürlich
alle Primzahlen der Größe nach aufsteigend angeordnet), so können wir diese
mit Hilfe der Funktion "ithprime" finden. Die Funktion "ithprime" erhält stets ein
Argument: Eine positive ganze Zahl i, d.h. also ein Aufruf ist immer von der Form
"ithprime( i )". Als Rückgabewert liefert uns die Funktion ithprime die i-te Primzahl.
Wir bestimmen die 1000. Primzahl, die 5000. Primzahl und die 123456. Primzahl:
ithprime(1000)
ithprime(10000)
ithprime(123456)
Die erste Funktion, die wir in diesem Abschnitt kennengelernt haben, war die
Funktion "isprime" zum Test, ob eine Zahl eine Primzahl ist oder nicht.
Haben wir von einer Zahl festgestellt, dass es sich nicht um eine Primzahl handelt,
so muss die betrachtete Zahl zusammengesetzt sein, d.h. sie ist in ein Produkt
von Primzahlpotenzen zerlegbar. Man spricht davon, dass sich die Zahl "faktori-
sieren" lässt.
Die Faktorisierung einer ganzen Zahl kann in MuPAD mittels der Funktion "ifactor"
berechnet werden. Leider sind Faktorisierungsalgorithmen nicht annähernd so
effizient, wie zum Beispiel einige der Algorithmen, die testen ob eine gegebene
Zahl eine Primzahl ist.
Daher: Bei der Berechnung der Faktorisierung großer Zahlen benötigt man auch
in MuPAD Geduld (auf dieser "Ineffizienz" von Faktorisierungsalgorithmen beruht
übrigens entscheidend die Sicherheit vieler Verfahren in der Kryptographie - so
z.B. auch die Sicherheit von RSA).
Die Funktion ifactor erhält stets ein Argument: Eine positive ganze Zahl a, d.h.
also ein Aufruf ist immer von der Form "ifactor( a )". Als Rückgabewert liefert uns
die Funktion ifactor die Faktorisierung der Zahl a, falls a zusammengesetzt (also
kein Primzahl) ist, und a, falls a eine Primzahl ist.
Nun zu einigen Beispielen:
ifactor(64)
ifactor(124)
ifactor(15254727)
ifactor(74757235275979)
ifactor(33333333)
Anstelle von "ifactor" kann man auch die Funktion "factor" aufrufen. Dann muss
allerdings das System intern erst feststellen, dass es sich bei den Eingaben um
ganze Zahlen handelt (denn mit "factor" kann man z.B. auch Polynome faktori-
sieren). Wenn man also wirklich effizient und schnell große ganze Zahlen faktori-
sieren möchte, so sollte man die Funktion "ifactor" verwenden, um nicht unnötig
Rechenzeit für sogenannte interne Typ-Überprüfungen zu verschwenden.
________________________________________________________________________________
Übungen:
1. Ist 32765487239865 eine Primzahl? Wenn nein, so berechnen Sie die Primfaktorzerlegung dieses
__Zahl. Welche Primzahl ist die nächste, die auf 32765487239865 folgt?
_______________________________________________________________________________
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.
_______________________________________________________________________________