Introduzione a PARI / GP - Dipartimento di Matematica

Università degli studi di
Milano
Dipartimento di Matematica «F. Enriques»
Progetto lauree scientifiche
Laboratorio di crittografia
Introduzione a PARI / GP
pari / gp è una libreria per linguaggi ad alto livello (ad es. C, C++, Pascal, Fortran) ed
una sofisticata calcolatrice programmabile. Le sue caratteristiche principali sono l’essere
un programma libero, la rapidità (da  a  volte più rapido di altri programmi), la
possibilità di usare tipi di dati comuni nell’uso matematico, e l’esteso supporto per la
teoria dei numeri. pari / gp funziona su molte versioni di Unix (inclusi Linux e OS-X) ed
ha un supporto sperimentale per Windows; può essere scaricato liberamente da http:
//pari.math.u-bordeaux.fr
 Iniziamo!
Dopo aver acceso il computer, al prompt, digitiamo gnome e premiamo <invio>. [rimosse le istruzioni su nome utente e password da utilizzare sui terminali del laboratorio del
dipartimento] Una volta finito di caricare l’ambiente grafico, aprite il terminale, digitate
gp e poi di nuovo <invio>. Dovrebbe comparirvi un ?
Scrivete 2+2 e poi premete <invio> (questa è l’ultima volta che lo specificherò). Dovreste vedere:
? 2+2
%1 = 4
?
%1 significa che questo è il primo risultato, e che è uguale a . Forse siete abituati a
terminare ogni riga col ;
? 2+2;
?
Cos’è successo?!? Qui il segno ; serve per separare due istruzioni, e come effetto collaterale non stampa il risultato: è utile se abbiamo dei numeri giganteschi, ma vedremo più
avanti. . .
Proviamo ora qualche altra operazione
? 12-3
%3 = 9
? 1-7*4+2
%4 = -25
? 8/2
%5 = 4
Progetto lauree scientifiche
Laboratorio di crittografia
? 3/2
%6 = 3/2
Notiamo che pari / gp usa tranquillamente le frazioni.
? 2^5
%7 = 32
? (-1/2)^3
%8 = -1/8
? %^(1/3)
%9 = 0.2500000000000000000000000000 + 0.4330127018922193233818615853*I
?
La prima operazione è un elevamento a potenza. Nel secondo caso è necessario usare le
parentesi. Il terzo caso è un po’ strano: il segno % indica l’ultimo risultato, in questo caso
−/. L’elevamento alla potenza /, come sapete, corrisponde all’estrazione di radice
cubica: ma cos’è il risultato? Be’, se provate ad elevarlo alla terza otteniamo:
? %^3
%10 = -0.1250000000000000000000000000 + 4.73316542 E-30*I
Se guardate attentamente, noterete che questo risultato è un’approssimazione reale di
−/ più un numero molto piccolo per I: pari / gp ha calcolato una radice complessa di
−/, la cui terza potenza è ancora un numero complesso. Ma procediamo oltre: il resto
della divisione fra a e b è indicato così:
? 13%3
%11 = 1
? 13%5
%12 = 3
divrem
Se vogliamo conoscere sia il quoziente che il resto, usiamo la funzione divrem
? divrem(13,5)
%13 = [2, 3]~
gcd
bezout
Per aiutarci a comprendere il significato del risultato, scriviamo ?divrem. Scopriamo così
che [2,3]~ è un vettore colonna (la tilde indica che è stato scritto come riga). Per verificare provate a calcolare: ∗+. Altre funzioni utili sono gcd e bezout: provate a scoprire
cosa fanno.
Esercizio . Calcolate: ( −)/; +  ; MCD(, ); MCD(, ); trovate ora x, y ∈ Z tali
che MCD(, ) = x + y; idem per MCD(, ) = x + y.
 Moduli
Se vogliamo calcolare  mod , cioè la classe di resto di  modulo , possiamo fare
così:

Introduzione a PARI / GP
? 3^123
%14 = 48519278097689642681155855396759336072749841943521979872827
? % %17
%15 = 7
Proviamo con numeri ancora più grossi:  mod 
? 1435^467
%16 = 1777615382246166178183410278313640776056638142669953819537560638
4440658254724148151873065978590741557038852046453447172605903966524399
3282526617824036893640611161880745082059189693057609522158693080432443
9998398836975623428194912933179425712057461415130444524580749980805005
8509867127417336379682306411510441154004626826306562934477025796842756
6122648440668126135687775339293954033451823669552803135626101640029821
6739165699202497760856493541256340994201027150885944297925893515077793
7150399397095459918937650074934176426881767936613106102510426319567001
0994996371452394390119908181445633782348077580430491526771051683640672
4971264931807444956409070109368165019674558692845735859148710514555170
4827720056862222151684171697723531459399418362761150767740201368452163
3098976436853213188768138997862446878783257000042344671019537172694332
9829289524670282277082018477544775532337203726689402339317171851051173
1888675886503564085228875554538859323656362277372494014604537852664463
5722523401406637257509915035234834445920788182674320824257475653017329
3786580558425511337908137272201426637018341483418690947751236778336073
8670206740415366955901542770191159203252282313353796838073742788507484
7935413477057905621326271496461158235016122932938889520896833009552098
6616174185149395675553335866572964314749067105608434617808430924522024
3935739714650595444706938780982421686356526341266574945028849139621682
1878672534002731178309209364946031679431334704410971880861325189471244
81201171875
? %%147
%17 = 49
Umph! Forse era meglio usare il ;
? 1435^467;
? % %147
%19 = 49
Meglio, ma se usassimo numeri ancora un poco più grandi, inizieremmo a trovare cose troppo grandi, e avremmo dei problemi. D’altro canto a noi non serve veramente
calcolare  come numero intero: sarebbe sufficiente ridurre modulo  ad ogni
passaggio.
? Mod(1435,147)
%20 = Mod(112, 147)

Progetto lauree scientifiche
Laboratorio di crittografia
? %^467
%21 = Mod(49, 147)
Mod
nextprime
Mod crea un intero modulare: Mod(1435,147) è la classe di resto di  mod . Notiamo che  ≡  mod , cioè Mod(1435,147) e Mod(112,147) sono la stessa classe di
resto.
Vediamo un altro esempio. Attiviamo ora il timer dando l’istruzione #, cerchiamo un
primo grande con nextprime, e poi confrontiamo i due modi per svolgere un elevamento a potenza.
? #
timer = 1 (on)
? p=nextprime(10^5)
time = 0 ms.
%22 = 100003
? e=8234325
time = 0 ms.
%23 = 8234325
? 2^e %p
time = 16 ms.
%24 = 6033
? Mod(2,p)^e
time = 0 ms.
? #
timer = 0 (off)
lift
Variabili
Un’ultra istruzione utile è lift: dato una classe di resto modulo n, restituisce l’unico
intero nell’intervallo [, n) della classe:provate a giocarci.
Vediamo ora come assegnare un nome agli oggetti
? a=Mod(1435,147)
%25 = Mod(112, 147)
a può ora essere usato al posto di Mod(1435,147)
? a+Mod(3,147)
%26 = Mod(115, 147)
? a+3
%27 = Mod(115, 147)
? 2*a
%28 = Mod(77, 147)
? a^2
%29 = Mod(49, 147)
? a^(-1)
*** impossible inverse modulo: Mod(7, 147).
? (a+3)^(-1)
%30 = Mod(124, 147)

Introduzione a PARI / GP
Non siamo riusciti a calcolare a − : infatti MCD(a, ) = , per cui non può esistere b tale
che ab ≡  mod . Se volessimo sapere quante sono le classi di resto invertibili mod ,
basterebbe usare la funzione eulerphi, che calcola la φ di Eulero:
eulerphi
? eulerphi(147)
%31 = 84
 Programmazione
Abbiamo visto come creare delle variabili. Vediamo ora qualche semplice modo per programmare pari / gp.
Il modo più semplice per definire una funzione è il seguente: f(x)=x^2-1. Ora possiamo calcolare f (x) per un qualsiasi x
Funzioni
? f(1)
%32 = 0
? f(-2/3)
%33 = -5/9
? f(4.3)
%34 = 17.48999999999999999999999999
? f(a)
%35 = Mod(48, 147)
Funzioni più complicate vengono definite in modo simile: ogni istruzione è separata da
; e il risultato della funzione è il risultato dell’ultima assegnazione
? modinv(a,n)=local(phi);phi=eulerphi(n);Mod(a,n)^(phi-1)
? modinv(115,147)
%36 = Mod(124, 147)
? modinv(112,147)
%37 = Mod(49, 147)
? %*112
%38 = Mod(49, 147)
L’istruzione local serve per segnalare che phi è una variabile locale; le variabili a ed n lo
sono automaticamente per come è definita la funzione modinv. Ricordiamo che a φ(n) ≡
 mod n per ogni a relativamente primo ad n, e che quindi a φ(n)− ≡ a − mod n. Sopra
verifichiamo come questo non sia vero se a ed n non sono relativamente primi.
Supponiamo ora di voler vedere com’è fatta la funzione inversa: prendiamo n = : è un
numero primo, per cui ogni classe di resto — tranne quella nulla — è invertibile.
? n=5
%39 = 5
? for(i=1,n-1,a=Mod(i,n);b=a^-1;print(a,"\t",b))
Mod(1, 5)
Mod(1, 5)
Mod(2, 5)
Mod(3, 5)

local
Progetto lauree scientifiche
Mod(3, 5)
Mod(4, 5)
for
print
Laboratorio di crittografia
Mod(2, 5)
Mod(4, 5)
Vi consiglio di controllare la definizione di for e di print. L’istruzione "\t" rappresenta
un tabulatore. Analogamente
? for(i=1,n-1,a=Mod(i,n);b=f(a);print(a,"\t",b))
Mod(1, 5)
Mod(0, 5)
Mod(2, 5)
Mod(3, 5)
Mod(3, 5)
Mod(3, 5)
Mod(4, 5)
Mod(0, 5)
if
Supponiamo di voler trovare, se esiste, un x tale che f (x) ≡  mod : stampare l’intera
tabella porterebbe via troppo spazio, e poi sarebbe scomodo scorrerla alla ricerca del
valore cercato. Usiamo un test condizionale: l’istruzione if
? n=147;for(i=0,n-1,a=Mod(i,n);b=f(a);if(b==Mod(1,n),print(a,"\t",b)))
Non esiste un tale x! Proviamo a risolvere l’equazione f (x) = :
? n=147;for(i=0,n-1,a=Mod(i,n);b=f(a);if(b==Mod(3,n),print(a,"\t",b)))
Mod(2, 147)
Mod(3, 147)
Mod(47, 147)
Mod(3, 147)
Mod(100, 147)
Mod(3, 147)
Mod(145, 147)
Mod(3, 147)
Notiamo come ci siano quattro soluzioni ad un’equazione di secondo grado!
Esercizio . Sia f (x) = x  − x  + . Calcolate il valore di f per ogni classe di resto modulo
. Cercate poi eventuali soluzioni alle equazioni f (x) ≡ , f (x) ≡ −, f (x) ≡  mod .
