Pari ist ein Algebrasystem aus Frankreich. Es ist ein Kommandozeilenprogramm, das heißt es besitzt keine grafische Oberfläche. Pari ist sehr mächtig. Es beherrscht neben den Grundrechenarten auch zahlentheoretische Funktionen und Funktionen zu Elliptischen Kurven, Zahlenfeldern, Polynomen, Vektoren und Summen, Produkte und Integrale.
Bildschirmfoto des Pari/GP Logos
Pari ist zum Beispiel auch im Bereich der Kryptographie, die ja sehr Mathematik-lastig ist, beliebt. So kann man dort sehr einfach Modulo und somit auch in Primen Restklassengruppen rechnen. Im Nachfolgenden möchte ich anhand einiger Funktionen Pari/GP vorstellen.
Aufgabe: Es soll aus einem öffentlichen RSA-Schlüssel (n,e) = (2417449,11) und dem Chiffretext c = 11 der Klartext zurückberechnet werden. Dazu verwenden wir Pari.
Es gilt: n = p*q. Wir wollen p und q berechnen durch Faktorisieren.
(16:16) gp > factor(2417449)
%1 =
[1531 1]
[1579 1]
Damit haben wir die Primzahlen p = 1531 und q = 1579 berechnet.
Nun müssen wir phi(n) = (p-1)(q-1) berechnen. Die Funktion φ (Phi) steht hier für das Eulerphi und kann mit einer extra Funktion in Pari berechnet werden.
(16:31) gp > eulerphi(2417449)
%2 = 2414340
Die Zahlen mit dem Prozentzeichen davor (%2) sind übrigens Synonyme für die Zahlen und können bei weiteren Berechnungen statt der Zahl selbst verwendet werden. Als nächstes müssen wir, um an den Exponenten d zu kommen, mit dem bei RSA entschlüsselt wird, die Linearkombination von c und phi(n) berechnen. Diese kann man von Hand normal mit dem Erweiterten Euklidschen Algorithmus berechnen. Pari macht das mit einer kleinen Funktion.
(16:37) gp > bezout(11,%2)
%3 = [438971, -2, 1]
Die Linearkombination von 11 und 2414340 ist also 438971 und -2. Der Erweirterte Euklidsche Algorithmus rechnet mit dem Größten Gemeinsamen Teiler ggt() (im Englischen gcd für greatest common divisor). Nun haben wir unseren Entschlüsselungs-Exponenten d berechnet. Rechnen wir nun unseren Chiffretext hoch d modulo n bekommen wir unseren Klartext. Für solche Berechnungen muss bei Pari immer das Objekt Mod(x,y) verwendet werden. Wobei x die Zahl und y den Modul darstellt.
(16:42) gp > Mod(11^438971,2417449)
%4 = Mod(2349316, 2417449)
Unser Klartext ist also m = 2349316.
Das ist nur ein kleiner Teil des Repertoires, dass Pari beherrscht. Vor allem ist ein großer Vorteil von Pari, dass es mit sehr großen Zahlen umgehen kann. So ist es ein leichtes zum Beispiel 22048 zu berechnen.
(16:48) gp > 2^2048
%5 =
3231700607131100730071487668866995196044410266971548403
2130345427524655138867890893197201411522913463688717960
9218980194941195591504909210950881523864482831206308773
6730099609175019775038965210679605763838406756827679221
8642619756161838094338476170470581645852036305042887575
8915410658086075523991239303855219143333896683424206849
7478656456949485617603532632205807780565933102619270846
0314150258592864177116725943603718461857357598351152301
6459044036976132332872312271256847108202097251571017269
3132346967854258065669793504599726835299863821552516638
9437335543602135433229604645318478604952148193555853611
059596230656
Diese Zahl wird in nullkommanichts von Pari berechnet und stellt nur eine kleine Zahl dar.
Nun möchten wir die Taylor-Entwicklung (fünftes Taylor-Polynom) von ln(x+1) berechnen. Das geht in Pari wie folgt:
(17:01) gp > taylor(log(x+1),x)
%15 = x - 1/2*x^2 + 1/3*x^3 - 1/4*x^4 + 1/5*x^5 - 1/6*x^6 + 1/7*x^7 - 1/8*x^8 + 1/9*x^9 - 1/10*x^10 + 1/11*x^11 - 1/12*x^12 + 1/13*x^13 - 1/14*x^14 + 1/15*x^15 + O(x^16)
Wir wollen den größten gemeinsamen Teiler von 5 und 15 berechnen.
(17:06) gp > gcd(5,15)
%16 = 5
Angenommen wir haben die Zahl 203949032409 und möchten die nächst höhere Primzahl bestimmen, dann geht das in Pari wie folgt:
(17:13) gp > nextprime(203949032409)
%17 = 203949032429
Du willst prüfen ob eine Zahl prim ist, dann geht das in Pari mit der Funktion isprime(x). Allerdings ist hierbei zu berücksichtigen, dass man nur durch ausprobieren aller Zahlen bis x/2 als Teiler von x wirklich sicher testen kann, ob x eine Primzahl ist (Probedivision). Andere mathematische Methoden sind (vor allem bei sehr hohen Zahlen) nicht immer zu 100 Prozent richtig oder sehr langsam, aber dennoch gut genug, um damit arbeiten zu können. Wir hatten oben die große Zahl 22048 die durch %5 repräsentiert wird. Nun wollen wir schauen ob diese Zahl prim ist. Natürlich wissen wir das schon vorher, da es sich um eine zweier Potenz handelt, muss sie durch zwei teilbar sein und ist damit keine Primzahl!
(17:13) gp > isprime(%5)
%18 = 0
Im Gegenzug muss die eben bestimmte nächste Primzahl größer 203949032409 (repräsentiert durch %17) ein anderes Ergebnis liefern. 0 steht hier für falsch (false) und 1 für wahr (true).
(17:18) gp > isprime(%17)
%19 = 1
Lust auf Pari bekommen? Pari ist kostenlos und wird auf pari.math.u-bordeaux.fr kostenlos zum Herunterladen zur Verfügung gestellt. Dieses mächtige Werkzeug kann z. Bsp. gut im Informatikstudium gebraucht, aber auch im Mathematikunterricht an Schulen eingesetzt werden.
Keine verwandten Beiträgen vorhanden.
hallo,
gibt es unter pari die möglichkeit, eine x-stellige zahl zu generieren, die nur 1er enthält?
Ein super Pari Experte bin ich leider nicht und hab deswegen auch keine wirkliche Methode. Vielleicht könnte man über eine Binärzahl gehen. Die Binärzahl mit 4 Einsen entspricht der dezimalen 15: 2^4 -1 = 15 => eine Binärzahl mit 4 Einsen. Wenn Du also eine Zahl mit x Einsen brauchst, könntest Du Versuchen die Binärzahl 2^x – 1 zu generieren, in dem Du die Dezimalzahl in eine Binärzahl umwandelst. Vielleicht klappt das? Da die Dezimalzahl wesentlich weniger Stellen benötigt, kommt dieser Weg mit wenig Ziffern aus.