________________________________________________________________________________
Inhalt....: Primzahlen in MuPAD
Kategorie.: Handwerkskasten
Mathematik: Zahlentheorie, Kryptographie
MuPAD.....: 3.0.0
Datum.....: 2002-08-14
Autoren...: Kai Gehrs <acrowley@mupad.de>
Funktionen: isprime, nextprime, ithprime, ifactor, factor
________________________________________________________________________________
Elementare MuPAD-Funktionen:
Primzahlen in MuPAD
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 Faktorisierung
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:
1. Argument: Eine positive ganze Zahl a
d.h. also ein Aufruf ist immer von der Form isprime( a ).
Als Rückgabewert 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 nicht prim ist (d.h. keine Primzahl 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:
Die Funktion nextprime erhält stets ein Argument:
1. 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:
1. 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 Notebook 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 "faktorisieren" läßt.
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 Krypto-
graphie - so z.B. auch die Sicherheit von RSA).
Die Funktion ifactor erhält stets ein Argument:
1. 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 muß
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
faktorisieren). Wenn man also wirklich effizient und schnell große ganze
Zahlen faktorisieren möchte, so sollte man die Funktion ifactor verwenden,
um nicht unnötig Rechenzeit für sogenannte interne Typ-Überprüfungen
zu verschwenden.
_______________________________________________________________________________
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.
_______________________________________________________________________________