1. Introduction
Contents
1. 1 mod n Si un de ces tests est faux on sait que n n est pas premier On pourra utiliser valuation et random voir l aide 7 LE MODE BIBLIOTH QUE Il nous reste d crire la fa on d acc der toutes ces fonctions en mode biblio th que 7 1 Fichiers include Afin d utiliser PARI en mode biblioth que il faut inclure le fichier pari pari h et linker avec la biblioth que libpari LE SYST ME PARI GP 19 7 2 Le type GEN Tous les objets PARI sont d un type unique savoir GEN qui est d fini comme un pointeur sur un long Chaque objet x de type GEN contient un premier mot de code x 0 contenant des informations principalement sur le type au sens GP de l objet ainsi que la taille etc Le contenu pr cis d pend du type consid r On renvoie au manuel et au code source pour tous les d tails 7 3 Philosophie g n rale PARI utilise une pile pour g rer l allocation dyna mique de m moire Chaque fonction est responsable de l allocation de la m moire de la valeur de retour mais aussi de la lib ration de la memoire utilis e par le calcul interm diaires La pile rend la gestion m moire tr s peu couteuse en temps et espace mais doit tre nettoy e manuellement PARI a choisi une philosophie d criture plus proche de l habitude convention nelle que celle de GMP L o GMP crit mpz_add x y z PARI crit x gadd y z Ce choix implique deux choses e Dans la tournure x gadd y z2. 45 24 vw C est un type obsol te Il vaut mieux utiliser t_POLMOD qui est un peu plus lent mais bien plus g n ral et pr te moins confusion 2 3 8 Le type t_POL Le type des polyn mes univari s Les coefficients peuvent avoir n importe quel type Les polyn mes multivari s sont implant s comme des polyn mes univari s coefficients polynomiaux L ordre des variables fonctionne sur le principe premier arriv premier servi l exception de la variable x pr d finie La fonction variable fournit les priorit s courantes des variables Une variable laquelle a t affect e une valeur peut encore tre appel e par x on peut donc r cup rer la variable par x x gp gt t Z y gp gt f z 3 t y t z 2 y 2 278 y t y z 2 La substitution d une expression une variable se fait par la fonction subst Mais on peut faire des substitutions plus volu es gr ce substpol et substvec gp gt subst f z t y 3 t 4 3 y t 3 3 y 2 y t 2 y 3 2 y 2 y t y73 gp gt substpol x 4 x 2 y 1 x 2 x 4 x 2 y x 1 gp gt substvec x y 2 z 3 x y z 1 x y xl 45 x 3 3 y 1 x 2 3 y 2 x y78 1 LE SYST ME PARI GP 11 Les fonctions suivantes permettent de manipuler des polyn mes univari s gcd factor factormod polcyclo poldisc polresultant polroots polroots mod polrootspadic polsturm polsym Faire 8 pour une liste Signalons une
3. l allocation du r sultat est op r e par la fonction gadd elle m me Ainsi l utilisateur n a t il pas se soucier d effectuer cette allocation De fa on g n rale seuls les objets construits la main par l utilisateur n cessitent d effectuer une allocation qui se fait alors par la commande cgetg taille type La taille d signe le nombre de mots r server pour l objet attention au x mot s de code et type peut tre t_INT t_REAL etc e Dans la tournure x gadd y gadd z t un objet interm diaire est cr qui ne sera pas accessible l utilisateur Il faut que l utilisateur g re lui m me l utilisation de la pile de m moire bloqu e par PARI 7 4 Gestion de la m moire Avant tout appel une fonction PARI il faut appeler la fonction pari_init Cette fonction se charge de bloquer un espace m moire d di PARI et de pr calculer un certain nombre de nombres premiers pari_init en particulier prend donc deux arguments soit l espace r server pour la pile et la limite des nombres premiers calculer L appel cr e en plus de la pile des constantes gen_0 gen_1 gen_m1i gen_2 etc et un vecteur de variables En outre un tas est cr contenant les objets universels qui ne doivent pas tre supprim s L tat courant de la m moire est fourni l utilisateur par la variable globale avma available memory address de type pari_sp stack pointer qui d cro t au fur et mesu
4. Remarque Dans ce document les sont utilis s pour couper les exemples qui d passent la largeur de la page mais gp pr sente les r sultats int gralement moins qu on ne lui demande de les couper n lignes via default lines n 2 gp LIGNE DE COMMANDE Cette partie a pour objectif de pr senter la calculette gp d en expliquer rapi dement le fonctionnement et les fonctionnalit s 2 1 Premiers pas g gt 1i ri h1 2 gp 101202 42 1 4 gp gt Pi 43 3 141592653589793238462643383 gp gt cos Pi 4 1 000000000000000000000000000 gp gt quit Goodbye Jusqu ici pas de surprises 2 2 Acc s l aide Premier objectif acc der la documentation Taper puis Enter affiche la liste des rubriques d aide et le mode d emploi de l aide tandis que affiche l int gralit du manuel Trois niveaux de documentation existent SOUS gp e fun donne une documentation minimale sur la fonction fun e fun affiche la partie du manuel correspondant la fonction fun dans une fen tre xdvi ou dans le terminal e mot cl indique les fonctions ayant un rapport avec le mot cl qui peut d ailleurs tre une expression arbitraire contenant ventuellement des espaces les guillemets sont optionnels si elle n en contient pas 4 LE SYST ME PARI GP Par d faut la recherche est restreinte au Chapitre 3 du manuel celui qui d crit les fonctions GP Si un est pr sent la f
5. fonction utile bas e sur des techniques de r duction des r seaux tant donn un polyn me irr ductible P Z X polred et polredabs cherchent un polyn me Q petits coefficients qui d finisse la m me extension que P c est dire tel que Q X P Q X Q L option 1 de polred ou polredabs fournit en plus l isomorphisme permettant de passer d une racine de P une racine de Q gp gt P x 3 371025000 x 2 45886547466011250 x 1891675437731848027406250 gp gt Q polredabs P 2 x73 2 x 2 gp gt V polredabs P 1 43 x 3 2 xx 2 Mod 123675 x 123675000 x 3 2xx 2 gp gt subst P x V 2 44 0 gp gt modreverse V 21 5 Mod 1 123675x x 1000 x 3 371025000 xx 72 458865474 gp gt subst Q x 4 46 0 2 3 9 Le type t_POLMOD C est l quivalent du type t_INTMOD pour les poly n mes qui permet de construire des extensions alg briques d alg bres gp gt Mod x 3 x 7 1 41 Mod x 3 x 7 1 gp gt 1 4 42 Mod x 4 x 7 1 gp gt chinese Mod x 2 x 3 1 3 Mod x 8 x74 x x710 x 7 x73 1 Exercice Calculer l inverse dans F4 F2 X X X 1 de l l ment X En d duire qu il est ardu d utiliser gp pour les calculs dans les corps finis non premiers Ceux qui ne sont pas convaincus peuvent calculer l inverse de Y 1 dans F6 Phare Y X Solution na ve gp gt T Mod 1 2 X 2 X 1 1 Mod X
6. gp gt f x y 1 z x 2 xy 4xz gp gt print f f 1 1 f 1 1 2 7 6 La valeur de retour d une fonction est celle de la derni re expression valu e dans celle ci On peut aussi utiliser explicitement return val qui interrompt l ex cution de la fonction et fixe la valeur de retour val En fait une fonction utilisateur n est rien d autre qu un objet de type t_CLOSURE assign une variable ordinaire Plut t que ce qui la construction ci dessus on peut utiliser la construction quivalente gp gt f x y 1 z gt x 2 y 4xz qui associe une fonction la variable f et m me utiliser des fonctions ano nymes sans leur donner de nom gp gt vecsort 3 2 11 1 3 1 2 gp gt vecsort 3 2 11 x y gt abs x abs y 2 1 2 3 Dans le dernier exemple on appelle une fonction de tri en lui imposant une fonction de comparaison explicite Le r sultat est un vecteur tri par ordre croissant des valeur absolues et non pas pour la relation d ordre ordinaire V MOV I 5 3 Boucles for La syntaxe GP d une boucle for est for X a b cmd Elle permet d ex cuter la suite de commandes cmd pour une valeur de la variable X allant de a b Ici cmd est une s quence de commandes s par es par des points virgules Signalons trois variantes utiles e fordiv n X cmd qui affecte la variable X les diviseurs successifs de n dans l ordre croissant et ex cute cm
7. 0659405015287 cos y2 0 624136994 print precision x precision x2 precision y precision y2 28 9 9 y2 precision y2 28 22026 60287475585937500000000 cos y2 0 6241406338839195625935912308 1e20 Pi 1e20 3 141592653 Noter que la pr cision de x2 est celle de x et non la pr cision courante Le type t_COMPLEX est de m me nature les pr cisions des parties r elle et imaginaire sont g r es ind pendamment 2 3 3 Le type t_PADIC C est le type utilis pour repr senter les nombres p adiques On les entre par x O p n o p n repr sente la pr cision p adique et x un entier ou un rationnel On peut faire de l arithm tique avec les p adiques quatre op rations racine n me et plus g n ralement factorisation de polyn mes dans Q X la plupart des fonctions transcendantes sont galement disponibles exp log logarithme d Iwasawa la fonction I de Morita la fonction de Kubota Leopoldt etc gP gt 1 8P 2 8P 3 8P 44 8P 5 MONVOUONVOUNUOV OU OV I 2748 0 2 12 272 273 274 275 277 279 2711 0 2 12 1729 0 2 15 1 276 277 279 2710 0 2 15 1 2 272 273 274 275 277 278 2710 0 2 12 1 27 92 97 1 1 2 275 276 0 278 factorpadic x 3 x 1 7 10 1 O 7710 xx 2 5x7 6 772 2x773 0 7710 1 1 O 7710 xx72 3 6 7 2x772 0 7710 1 2 3 4 Le typ
8. 2 2 2 2 2 2 2 8P 44 8P 5 14 LE SYST ME PARI GP gp gt M2 vecextract M 10 10 derni res colonnes gp gt matsize matkerint M2 46 20 10 Un point noter une commande qui se termine par un point virgule ne voit pas son r sultat affich toutefois celui ci reste num rot et disponible par son num ro 1 4 ici pour utilisation ult rieure Autre point noter les objets 4x ne peuvent tre modifi s gp offre en outre une implantation de l algorithme LLL accessible via qf111 Par exemple gp gt N 10720 1 0 0 round NxPi N 0 round Nxexp 1 0 N 1 1 0 0 314159265358979323846 100000000000000000000 0 271828182845904523536 O 100000000000000000000 gp gt U qf111 4 2 15431582173353 4771327925432 8876602352967 48479745189073 14989568758405 27886668740919 41947389406198 12969813997321 24129106874527 gp gt frac U 1 1 Pi 3 0 00000013326257 2 gp gt frac U 1 1 exp 1 4 0 000000032444343 Noter que qf111 renvoie une matrice U de d terminant 1 donnant une base LLL r duite en termes de la base canonique les vecteurs courts du r seau pro prement dits sont donn s par M qf111 M Parmi les autres applications signalons les fonctions algdep et lindep qui tentent de trouver une relation alg brique v rifi e par un r el ou un complexe ou une relation enti re v rifi e par un vecteur de flottants gp gt lindep log 15 lo
9. LE SYST ME PARI GP TABLE DES MATI RES 1 INTRODUCTION L objectif de ce texte est de pr senter le syst me PARI GP C est un survol ne pr tendant pas se substituer au volumineux manuel du syst me ni au tutoriel inclus dans ce manuel Pour toutes informations d ordre g n ral t l chargement documentation et Foire aux Questions on renvoie le lecteur la page du logiciel http pari math u bordeaux fr et aux Ressources PARI GP notamment une archive de scripts utiles http www math u bordeaux fr belabas pari PARI GP t d velopp partir de 1986 par un petit groupe anim par Henri Cohen l universit Bordeaux 1 C Batut C Bernardi H Cohen M Oli vier l origine comme outil d exp rience pour la recherche sur les algorithmes de la th orie des nombres Il a t repris en 1995 par Karim Belabas Paris XI puis Bordeaux qui le maintient depuis Le d veloppement est devenu plus ou vert licence GPL versions r guli res acc s aux versions de d veloppement Deux mailing lists existent depuis novembre 1997 pari users et pari dev et sont archiv es sur les sites sus mentionn s La version stable courante est la version 2 3 patchlevel 4 la date o ce texte est crit La version 2 4 3 au jour de l criture de ce texte est une version de d veloppement publique accessible via Subversion voir http pari math u bordeaux svn html PARI GP n cessite environ 3 Mo d espace
10. T 41 Mod Mod 1 2 X Mod 1 2 Mod 1 2 X 2 Mod 1 2 X Mod 1 2 gp gt 1 Mod Y 1 Y 2 Y X Mod 1 T x Mod forbidden division t_POLMOD t_POLMOD gp gt 1 Mod x 1 x 2 x X Mod 1 T A2 Mod Mod Mod 1 2 X Mod 1 2 Mod 1 2 X 2 Mod 1 2 X Mod 1 2 x Mod 1 Mod 1 2 X 2 Mod 1 2 xX Mod 1 2 x 2 12 LE SYST ME PARI GP Mod i Mod i 2 X 2 Mod i 2 X Mod 1 2 x Mod X Mod 1 2 X72 Mod i 2 X Mod 1 2 Le premier essai choue car les priorit s relatives des variables sont incor rectes puisque X lt Y gp interpr te Y 2 X x Mod 1 T comme X Y mod T qui est un l ment de F2 Y X T et non comme un l ment de F2 X T Y Le deuxi me essaie fonctionne car x lt X Solution volu e Plut t qu utiliser des t_POLMOD de t _POLMOD il est pr f rable de r aliser un gros corps fini par un l ment primitif sur son corps premier et y plonger les corps interm diaires gr ce polrootsff TRS gp gt T Mod 1 2 x x 2 x 1 gp gt U ffinit 2 4 y gp gt X polrootsff T 2 U 1 une racine de T dans F16 gp gt Y polrootsff x 2 x X 2 U 1 gp gt 1 Y 1 2 3 10 Le type t_SER Ce type permet de manipuler des s ries formelles lins tar des nombres p adiques une s rie formelle s entre comme P X O X o P est une fonction rationnelle On peut effectuer
11. d e forprime X a b cmd qui affecte X les nombres premiers successifs de l intervalle a b e forvec X m M cmd dans ce dernier cas m et M sont des vecteurs de m me dimension k et X parcourt le produit cart sien Jf mfi Mfi On pourra aussi consulter l aide de forstep forsubgroup Il est possible de modifier directement la valeur de X dans le corps de la boucle De plus X est locale la boucle et sa valeur initiale est restaur e en sortie de boucle 5 4 Tests La syntaxe de if est if test cmdi cmd2 La mention de cmd2 est facultative on peut donc crire if test cmd1 Si la condition test est vrai alors cmdi est ex cut e sinon cmd2 est ex cut s il est pr sent LE SYST ME PARI GP 17 GP comme C n a pas de type bool en le r sultat d un test gt lt est un entier sa valeur est vrai si cet entier est non nul faux sinon Ainsi if n i print i affiche i ssi il ne divise pas n Pi ge Il est facile de confondre et Comme en C la tournure if a b cmd1 cmd2 ex cute cmd1 si b ne s value pas 0 la valeur de retour de a b est b De m me if a 0 cmd1 cmd2 ex cute cmd2 Les op rateurs ET OU et NON se notent amp amp II le NON est prefixe comme suffixe il d signe la factorielle 5 5 Boucles while et until Ces deux boucles s crivent while a cmd et until a cmd La suite de commandes cmd est ex cut e tant que a est non nul o
12. disque et 4 Mo de m moire vive pour fonctionner correctement Il est crit en C donc tr s portable suppl ment d un noyau assembleur pour l arithm tique sur les architectures courantes donc sans sacrifier l efficacit PARI GP supporte l utilisation de GMP pour l arith m tique enti re la place du noyau natif Des versions binaires sont disponibles pour les syst mes les plus courants Linux Windows Date 08 janvier 2010 115 Mo pour la version Windows 2Les d veloppeurs n ont connaissance d aucun syst me moderne disons de moins de 20 ans d ge sur lequel gp ne tourne pas Le noyau GMP est l g rement plus lent faible pr cision l g rement plus rapide partir de 100 chiffres d cimaux deux fois plus rapide partir de 300 chiffres cinq fois plus rapide vers 2000000 chiffres 1 2 LE SYST ME PARI GP 1 1 Pr sentation g n rale Le syst me PARI GP comme son nom l indique comporte deux parties e La premi re PARI est une biblioth que de fonctions C orient e vers la th orie des nombres e La seconde gp est un interpr teur qui permet d acc der depuis une ligne de commande de syntaxe simple l ensemble des fonctionnalit s de PARI Cet interpr teur est programmable dans le langage de script GP L int r t est d offrir d une part une calculette intuitive pour des non experts en programmation qui permet toutefois d acc der la quasi totalit des fonc tion
13. e avma et 1bot mais si certains de ses composants sont situ s entre lbot et ltop une erreur est soulev e par gerepile C est possible par exemple avec un vecteur GEN fun GEN x GEN y GEN z pari_sp ltop avma lbot GEN vec t gadd x gmul y z lbot avma vec cgetg t_VEC 4 gel vec 1 x gel vec 2 t gel vec 3 gadd t z return gerepile ltop lbot vec Ce code produit une erreur significant pointers lost in gerepile en effet si vec est pr serv sa deuxi me composante est effac e Exercice Comment corriger le code ci dessus Quelques variantes de gerepile qui suffisent en g n ral e gerepileupto pari_sp ltop GEN q nettoie la pile entre 1top et q et renvoie q mis jour Attention pour que cette syntaxe fonctionne q doit avoir t cr avant ses composants comme dans l exemple plus haut LE SYST ME PARI GP 21 e gerepilecopy pari_sp ltop GEN x est fonctionnellement quivalent l instruction gerepileupto ltop gcopy x quoique plus rapide on met x en s curit on nettoie la pile de 1top la position courante et on renvoie la nouvelle adresse de x e gerepileall pari_sp ltop int n permet de nettoyer la pile entre ltop et la position courante Les n objets dont les adresses suivent sont pr serv s et leurs adresses mises jour Par exemple gerepileall itop 3 amp x amp y amp z 11 Les deux fonctions les plus lentes sont gerepilecopy et ge
14. e la fa on dont gp g re la pr cision La pr cision courante s obtient par p gp gt p realprecision 28 significant digits MOV I Cette pr cision affecte l affichage des r sultats et la conversion de donn es exactes en flottants dont les composantes de bas niveau sont de type t_REAL Par contre un calcul utilisant des donn es flottantes est effectu la pr cision des donn es ind pendamment de la pr cision courante m me si seuls les chiffres correspondant la pr cision courante sont affich s De m me si un r sultat a moins de chiffres significatifs que la pr cision courante seuls ceux ci sont affich s Finalement ap pliquer une fonction dont le r sultat est flottant des donn es exactes n cessite une conversion pr liminaire et le calcul s effectue donc la pr cision courante y compris les constantes Pi Euler Voyons comment ces r gles s appliquent sur quelques exemples gp gt x Pi 2 exp 10 1 1 570750926865134134379786100 gp gt p 9 realprecision 9 significant digits gp gt y Pi 2 exp 10 2 1 57075093 gp gt x2 tan x 3 22026 4658 gp gt y2 tan y 4 22026 6029 gp gt p 28 LE SYST ME PARI GP realprecision 28 significant digits 8P 5 8P 6 8P T 8P 8 8P VUNVMUNVN UV NV 28 gP gt 9 gP gt 10 gP gt 11 x2 22026 46577967340659405015287 y2 22026 60286 tan x 22026 4657796734
15. e t_INTMOD C est le type des l ments de Z NZ On cr e un tel l ment par Mod x N Diverses fonctions s appliquent ces l ments issquare sqrt chinese fonctions arithm tiques LE SYST ME PARI GP 9 gp gt issquare Mod 2 2 127 1 1 1 gp gt lift sqrt Mod 2 2 127 1 42 18446744073709551616 gp gt chinese Mod 2 10 Mod 3 13 43 Mod 42 130 gp gt chinese Mod 2 10 Mod 3 5 x chinese incompatible arguments in chinois gp gt a Mod 5 143 7 4 Mod 47 143 gp gt b 1 Mod 7 eulerphi 143 5 Mod 103 120 gp gt a 103 46 Mod 5 143 gp gt a lift b 7 Mod 5 143 Pour convertir un l ment de type t_INTMOD en entier usuel on utilise la fonc tion lift qui donne le rel vement canonique dans 0 N 1 de l l ment ou centerlift qui donne le rel vement centr dans N 2 N 2 Calculons main tenant une racine primitive modulo 101 et r solvons un probl me de log discret dans le groupe multiplicatif du corps premier Z 101Z gp gt g znprimroot 101 41 Mod 2 101 gp gt g znlog 7 g h2 9 gp gt 879 3 Mod 7 101 La fonction znstar permet d obtenir la structure de Z NZ m me quand il n est pas cyclique 2 3 5 Le type t_FRAC Nombres rationnels la fraction est r duite au plus petit d nominateur La fraction continue d un nombre r el ou d une fraction peut tre obtenue via contfrac contfracpnan la premi
16. en obtenir une liste List of the PARI types t_INT long integers codi cod2 man_1 man k t_REAL long real numbers codi cod2 man_i1 man k t_INTMOD integermods code mod integer t_FRAC irred rationals code num den t_FFELT finite field elt code cod2 elt mod Cp t_ COMPLEX complex numbers code real imag t_PADIC p adic numbers codi cod2 pl p r int t_QUAD quadratic numbers codi mod real imag t_POLMOD poly mod code mod polynomial t_POL polynomials codi cod2 man_1 mank t_ SER power series codi cod2 man 1 man_k t_RFRAC irred rat func code num den t_QFR real qfb code a b c del t_QFI imaginary qfb code a b c t VEC row vector code x1 xk t_COL column vector code st xk t_MAT matrix code col_1 col k t_ LIST list code n nmax vec t_STR string code man_1 man k t_VECSMALL vec small ints code x_1 x_k t_CLOSURE functions code arity La fin de la ligne d crit la structure C des l ments du type donn par exemple pour le type t_INT les deux premiers mots sont des mots de code et les mots suivants repr sentent la mantisse Pour le type t_FRAC le premier mot es
17. fonctionnalit s utiles dans ce dernier cas la commande permet de conna tre le temps CPU utilis par la derni re commande gp gt xxx last result computed in 210 ms De fa on analogue la commande d clenche un chronom tre de sorte que le r sultat de chaque calcul s affiche avec le temps qu il a pris Un nouveau inter rompt le chronom tre Enfin la commande gn o n est un entier entre 0 et 10 d clenche des messages de diagnostic qui permettent de suivre le d roulement d un calcul un peu long Dans la factorisation ci dessus g3 g4 g5 g6 g8 permettent d acc der des niveaux diff rents Dans le cas de la factorisation on peut voir la suite des algorithmes utilis s na f p SQUFOF ECM MPQS Les options de factorint permettent d influer sur ces diff rentes m thodes gp gt factorint factorint x flag 0 factor the integer x flag is optional whose binary digits mean 1 avoid MPQS 2 avoid first stage ECM may fall back on it later 4 avoid Pollard Brent Rho and Shanks SQUFOF 8 skip final ECM huge composites will be declared prime L expression entre accolades dans le prototype de la fonction indique que cet argument est optionnel la valeur transmise si l argument flag est omis est 0 l instar de factorint un grand nombre de fonctions GP ont des arguments facultatifs qui permettent de pr ciser l algorithme utilis ou des param tres uti lis s par cet algorit
18. g 3 log 5 1 1 1 1 7 gp gt polroots x 3 x 1 42 1 324717957244746025960908854 0 E 28 I gp gt sqrt 1 43 1 150963925257758035680601218 I gp gt algdep 8 4 x 6 x 2 1 LE SYST ME PARI GP 15 Noter qu il faut donner algdep une borne sur le degr de la relation trouver 3 FONCTIONS SUR LES CORPS DE NOMBRES Il semble important de consacrer une t te de section f t elle courte ces fonc tionnalit s qui sont le fer de lance de PARI et sa principale originalit Toutefois expliquer le r le de ces diff rentes fonctions et la nature des objets qu elles cal culent d passe largement le cadre de cet expos Signalons juste que 6 permet d acc der une liste Pour le reste on renvoie par exemple au tutoriel de la distribution aux livres d Henri Cohen et au survol 4 FONCTIONS DIVERSES GP offre un grand nombre de fonctions d int gration et de sommation num rique limit es aux cas univari La plupart d entre elles sont tudi es pour le calcul grande pr cision Leur comportement est tr s convenable sur les fonctions simples gp gt p105 gp gt intnum x 1 2 1 x 2 1 2 41 0 E 106 Par contre elles sont tr s sensibles aux singularit s ainsi qu au comportement asymptotique des fonctions oscillantes Il est donc pr f rable d indiquer explici tement les probl mes sous peine de r sultats ridicules oo 1 defi
19. hme Par exemple la fonction factor gp gt factor factor x lim factorization of x lim is optional and can be set whenever x is of possibly recursive rational type If lim is set return partial factorization using primes up to lim up to primelimit if lim 0 LE SYST ME PARI GP 7 Ainsi factor x tente de factoriser compl tement x mais factor x 10 5 se contente de rechercher les facteurs premiers inf rieurs 10 Quelques autres fonctions GP manipulant les entiers sont bezout core coredisc divisors eulerphi gcd isprime lcm sigma sqrtint No ter que la fonction isprime contrairement la majorit des syst mes de calcul formel prouve la primalit du nombre m thodes N 1 et APRCL plut t que d utiliser une batterie de tests probabilistes comme le fait ispseudoprime Exercice Consulter l aide de la fonction sigma Calculer la somme des carr s des diviseurs de 2 1 Est il fait appel la factorisation pour effectuer ce calcul Combien de temps faut il 2 3 2 Les types t_REAL t_COMPLEX Le type t_REAL est utilis pour repr senter des nombres r els en pr cision arbitraire Les fonctions transcendantes habituelles peuvent tre utilis es pour manipuler ces nombres Faire 3 pour obtenir une liste Les constantes Euler Pi sont pr d finies gp 1 V cos Pi 1 000000000000000000000000000 gp gt gamma 1 2 72 2 3 141592653589793238462643383 Il convient de dire un mot d
20. in du mot cl au contraire la recherche est tendue l int gralit du manuel gp gt GRH bnfcertify bnfinit bnfisintnorm bnfisnorm quadclassunit rnfisnorm thue thueinit See also Functions related to general number fields gp gt elliptic curve Chapter 1 Arithmetic functions Chapter 2 See also Member functions Specific Use of the kbd gp Calculator Chapter 3 elladd ellak ellan ellap ellbil ellchangecurve elleisnum ellglobalred ellhe ight ellinit ellisoncurve elllocalred ellminimalmodel ellorder ellpointtoz ellpow ellrootno ellsub elltaniyama elltors ellwp See also Functions related to elliptic curves Functions related to general number fields 2 3 Les types GP GP n est pas typ au sens informatique du terme en par ticulier les variables n ont pas de type Cependant chaque objet GP a un type interne sp cifique qui peut tre visualis en utilisant la fonction type Par exemple on obtient gp gt type 3 41 t_INT Chaque r sultat renvoy par gp se voit attribuer un num ro 1 ici Un r sultat pr c dent peut tre rappel par son num ro pr c d d un par exemple ici gp gt type 1 42 t_STR Le dernier r sultat peut tre rappel par l avant dernier par 4 l ant p nulti me par etc Ci dessus type aurait donn la m me r ponse LE SYST ME PARI GP 5 Pour ce qui est des types proprement dits la commande t permet d
21. les 4 op rations sur les s ries for melles les composer fonction subst en prendre l exponentielle le logarithme le cosinus etc On acc de au d veloppement limit des fonctions usuelles en les valuant en un param tre formel la pr cision des s ries formelles se g re comme pour les flottants en utilisant ps cette fois gp gt ps seriesprecision 16 significant terms gp gt cos x 1 1 1 2 x 2 1 24xx74 1 720 x 6 1 40320 x 8 1 3628800 x 10 1 479001600 x712 1 87178291200 x714 1 20922789888000 x 716 0 x 18 gp gt ps3 seriesprecision 3 significant terms gp gt sin x 42 x 1 6 x 3 0 x 4 Le premier calcul commence par la conversion x x O x 7 x 1 O x soit 16 termes significatifs ce qui permet d obtenir 16 termes de cos x 1 x et donc 18 termes dans le r sultat final 2 3 11 Le type t_RFRAC Ce type similaire aux type t_FRAC implante les fonc tions rationnelles 2 3 12 Les types t_VEC t_COL t_MAT La fa on la plus simple de construire un vecteur consiste saisir ses composantes entre crochets Un vecteur colonne est obtenu en transposant un vecteur ligne ce qui peut se faire soit par la fonction mattranspose soit par le suffixe gp gt v 1 2 3 1 1 2 3 LE SYST ME PARI GP 13 gp gt type 42 t VEC gp gt mattranspose 4 3 1 2 817 gp gt v 44 1 2 3 7 gp gt type 4 45 t_COL Une mat
22. nalit s de PARI et dispose d un langage de script permettant de r aliser des calculs moins l mentaires Et d autre part de pr server la possibilit de program mer en C une longue suite de calculs de bas niveau pour lesquels l efficacit est primordiale Dans cette optique signalons l outil gp2c crit par Bill Allombert qui tra duit les scripts GP en code C compilable avec la biblioth que PARI L interface gp2c run r alise m me ceci de fa on transparente elle traduit les scripts les compile et ex cute une session gp disposant au d marrage des nouvelles fonctions Cela permet souvent un gain important en vitesse lors de l ex cution par rapport l interpr tation du code GP sans nec ssiter d intervention sur un code C Remarque importante La syntaxe ainsi que les noms de fonction de GP ont norm ment chang entre les versions 1 xx avant 1996 et les versions 2 x x Ce document traite exclusivement des versions 2 x x 1 2 Fonctionnalit s 1 2 1 Ce que PARI GP sait bien faire Calculs l mentaires sur les entiers en pr cision arbitraire factorisation des entiers jusqu 80 chiffres environ fonc tions transcendantes calculs sur les polyn mes univari s factorisation recherche de racines complexes ou p adiques et les s ries formelles calculs l mentaires calculs sur les corps de nombres sa principale force calculs sur les courbes el liptiques alg bre lin aire sur Z Q ou un cor
23. nition pour all ger l criture p105 intnum x 0 oo sin x x Pi 2 2 20 78 n importe quoi intnum x 0 oo I1l sin x x Pi 2 3 0 E 105 parfait Ici le I signale que la fonction est oscillante de type f x sin x o f x tend lentement vers 0 Regarder intnum et sumnum pour la syntaxe et de nombreux examples puis 9 pour une liste compl te Finalement quelques fonctions graphiques sont disponible pour des trac s simples Voir 10 pour de plus amples renseignements 5 SCRIPTS GP Cette partie d crit les structures de contr le de GP qui permettent d crire de petits scripts On peut acc der une description compl te par 11 Ces structures sont voisines de celles de C 5 1 Variables Les variables peuvent hormis les noms r serv s porter n im porte quel nom compos de caract res alphanum riques plus le caract re _ commen ant par un caract re alphab tique L ensemble des noms r serv s inclut toutes les fonctions et constantes pr d finies 16 LE SYST ME PARI GP 5 2 Fonctions Les fonctions utilisateur sont simplement d finies par f args cmd o args est une liste d arguments un argument peut tre du type n 5 ce qui signifie que si l argument correspondant n est pas sp cifi par l utilisateur la valeur par d faut de n est 5 si un argument pour lequel aucune valeur par d faut n est donn e est omis par l utilisateur il prend la valeur 0
24. nsibles un bon principe consiste d clarer les variables locales comme telles en leur donnant la port e minimale possible si une variable tem poraire n est utile que dans le corps d une boucle la d clarer my pour la boucle Enfin pour utiliser une variable formelle x et viter les mauvaises surprises uti liser x 5 8 criture de scripts Un script peut se saisir directement dans une fen tre gp Pour viter que les retours chariots soient interpr t s et donc l ensemble de l expression valu e telle quelle on crit usuellement une fonction GP de la fa on suivante f x my y 1 Les retours chariots apr s le initial et l int rieur des accolades sont ignor s Il est en g n ral pr f rable de saisir le script dans un diteur de texte puis de lire le fichier correspondant par la commande r L appel f permet tout moment de r cup rer le code d une fonction crite pr c demment 6 LA PRATIQUE Exercice 1 crire un script qui prend en argument un entier n et renvoie le n me nombre de Fibonacci Exercice 2 crire un script qui effectue un produit de matrices Exercice 3 crire un script qui implante le test de primalit de Miller Rabin prenant en argument un entier n et un param tre p on crit n 1 25t et on tire successivement p valeurs de a 1 n 1 au hasard pour lesquelles on teste si at 1 mod n ou il existe k 0 s 1 tel que a
25. nt pas valides En contrepartie pour permettre des gains en efficacit certaines directives de compilation peuvent tre int gr es aux scripts pr cisant les types des objets manipul s e g le cas o un entier devrait tre stock dans un entier long du C Historique de ce document version 1 1 20 06 2004 G Hanrot document initial version 1 2 07 09 2004 K Belabas mise jour pari 2 2 8 version 1 3 10 10 2005 B Allombert K Belabas mise jour pari 2 2 11 version 1 4 08 01 2010 K Belabas mise jour pari 2 4 3
26. ps fini r duction des r seaux et principales applications 1 2 2 Ce que PARI GP sait faire Analyse num rique calcul int gral somma tion de s ries alg bre lin aire graphisme Toutes ces choses sont pr sentes soit par souci de compl tude soit parce qu elles ont un jour t n cessaires une appli cation particuli re mais ne constituent pas un objectif majeur de d veloppement et ne sont ce titre g n ralement pas optimis es 1 2 3 Ce que PARI GP ne sait pas faire Corps finis non premiers manipula tion de polyn mes multivari s manipulations d objets gigantesques milliards de chiffres dimension ou degr 10 toutes choses possibles dans le principe mais vite inutilisables et bien d autres choses encore LE SYST ME PARI GP 3 1 2 4 PARI GP n est pas un syst me de calcul formel Il ne sait ni repr sen ter ni manipuler des expressions autres que des fractions rationnelles ou s ries formelles ou des expressions alg briques sur ces domaines En particulier toute fonction transcendante est automatiquement remplac e par son d veloppement limit au voisinage de 0 gp gt sin x 1 x 1 6 x 3 1 120 x 5 1 5040 x 7 En arguant en outre du fait que le traitement des polyn mes multivari s ou des structures creuses dans PARI est rudimentaire PARI n est pas un syst me de calcul formel part enti re m me s il offre un certain nombre de fonctionnalit s formelles
27. re de l ex cution et pointe sur la fin de la zone de la pile encore disponible Les variables top et bot pointent vers le bas et le haut de la pile Il appartient l utilisateur de veiller nettoyer la pile p riodiquement cette fin plusieurs fonctions sont disponibles Le cas le plus simple est le cas o tous les r sultats calcul s entre deux points du code peuvent tre jet s il suffit de sauvegarder la valeur de avma en d but de section de code et de r affecter cette valeur avma la fin de cette section void affiche_add GEN x GEN y pari_sp ltop avma 20 LE SYST ME PARI GP output gadd x y avma ltop Parfois des calculs interm diaires sont n cessaires dont les r sultats doivent tre jet s sans d truire le r sultat final Il faut alors utiliser la fonction gerepile ou une de ses variantes Par exemple GEN add3 GEN x GEN y GEN z pari_sp ltop avma lbot GEN t gadd y z lbot avma return gerepile ltop lbot gadd x u La fonction gerepile ltop lbot t effectue les op rations suivantes e Elle ne modifie pas la zone m moire entre ltop et top e La zone m moire comprise entre avma et 1l1bot est d plac e en 1top les pointeurs sont mis jour e La zone situ e entre lbot et ltop est purement et simplement supprim e e La valeur de retour est la nouvelle adresse de l objet t Une difficult ne pas oublier si un objet PARI est situ entr
28. re fonction donne les quotients partiels la seconde les r duites partant des quotients partiels 2 3 6 Le type t_FFELT l ments d un corps fini On les construit l aide de ffgen et du polyn me minimal d un l ment primitif sur le corps premier souvent obtenu via ffinit gp gt T ffinit 3 4 t 1 Mod 1 3 t 4 Mod 1 3 t 3 Mod 1 3 t 2 Mod 1 3 t Mod 1 3 gp gt t ffgen T 82 t gp gt t 4 43 2 t 3 2 t 2 2 t 2 gp gt g ffprimroot t 10 LE SYST ME PARI GP h4 2xt72 t 1 gp gt fflog t g 45 48 gp gt g 48 6 t z Ceci construit un mod le F t T de F F1 par abus de langage on continue de noter t l image par la projection E de la variable de F ft mais le r sultat 3 montre bien qu il ne s agit pas d un polyn me ordinaire Puis on calcule un g n rateur g de F et on r soud un probl me de log discret dans ce groupe 2 3 7 Le type t_QUAD Le type t_QUAD permet de manipuler les l ments d ordres quadratiques On d finit l ordre par l appel la fonction quadgen qui prend le discriminant en argument et renvoie une valeur not e w On peut alors calculer sur les l ments du corps des fractions qui sont de la forme a b w gp gt s97 quadgen 97 Hi vw gp gt charpoly s97 2 x 2 x 24 gp gt 5 3 s97 3 5 3 w gp gt 72 14 241 39 w gp gt 59772
29. repileall par la recopie qu elles impliquent En contrepartie elles ne supposent rien sur la structure des objets qu elles mettent jour Exercice crire une fonction PARI qui prend en argument deux r els x et y et renvoie le vecteur x 2 y y 2 x Exercice crire une fonction PARI qui prend en argument un polyn me et un nombre r el et qui value le polyn me au point correspondant Exercice crire une fonction PARI qui implante le test de primalit de Miller Rabin On pourra utiliser la fonction Fp_pow 8 install ET gp2c Cette partie voque deux interfaces entre PARI et gp La fonction install permet d acc der un symbole d un fichier so depuis gp En particulier une fonction crite en PARI peut tre utilis e depuis gp Cette possibilit n existe pas sur certains vieux syst mes d exploitation par exemple Mac OS 9 et ne fonctionne g n ralement que dans le cas d un binaire gp dynamique L interface de cette fonction est d licate en particulier parce que le type des arguments au sens du C doit tre fourni install On renvoie au manuel pour les d tails Le compilateur gp2c permet de compiler des scripts GP vers PARI On constate des gains en efficacit significatifs d s lors que le code GP d origine est un tant soit peu complexe Noter que pour pouvoir compiler le langage de script GP il a fallu l affaiblir certaines syntaxes inutiles en principe en mode non interactif ne so
30. rice quant elle se saisit de la fa on suivante gp gt 1 2 3 4 5 6 7 8 9 46 1 2 3 4 5 6 7 8 9 gp implante bon nombre d op rations d alg bre lin aire sur un anneau euclidien ou un corps pivot de Gauss polyn me caract ristique d terminant HNF SNF noyau image etc Faire 8 pour une liste L acc s une composante d une matrice ou d un vecteur se fait via v i ou mli jl on peut galement utiliser m i resp m j pour acc der la i me ligne resp j me colonne de la matrice m La fonction vecextract permet en outre d extraire une partie d un vecteur ou d une matrice Les num ros de ligne et de colonne commencent 1 La longueur d un vecteur v s obtient par length v ou v Le nombre de colonnes d une matrice v s obtient avec la m me syntaxe il n y a pas de mani re naturelle d obtenir son nombre de lignes il faut utiliser matsize ou demander le nombre de colonnes de sa transpos e Une matrice ou un vecteur doit tre cr avant de pouvoir modifier ses entr es Faire v 1 2 sans avoir cr le vecteur v au pr alable cause une erreur On peut par exemple utiliser la commande v vector 15 ou M matrix 5 10 gp gt M matrix 20 20 j k gcd j k gp gt matdet M 12 46965467381760 gp gt factorint 4 43 2 32 MOV UN v 3 7 5 1 N M N 2 2 1 matdet N 346370321940480 matsnf M 4 720 24 24 24 12 12 4 4 4 2 2
31. t un mot de code le second mot contient l adresse du num rateur et le troisi me l adresse du d nominateur En GP cette structure C n est pas pertinente on acc de aux composantes d un objet naturellement pour les matrices M 1 21 ou les vecteurs v 1 par polcoeff pour les polyn mes les s ries ou les formes quadratiques binaires par imag ou real pour les nombres complexes ou quadratiques par denominator ou numerator pour les fractions et fonctions rationnelles et finalement lift x ou x mod pour le repr sentant canonique et le module associ s un type modulaire Il n y a pas de fa on simple d acc der aux mots de la mantisse d un r el ou d un entier une premi re approche utiliserait x ou bitand Examinons maintenant rapidement les diff rents types GP et les fonctions qui permettent de les manipuler 2 3 1 t_INT Ce type est utilis pour repr senter les entiers en pr cision arbi traire gp gt 450 11 17333687331126326593447131461045 6 LE SYST ME PARI GP gp gt 250 2 323285626090910773238208145520243 gp gt 200 3 78865786736479050355236321393218 gp gt 43 C 4 x 5 4 67985441606155742983110298166171 gp gt binomial 450 200 45 67985441606155742983110298166171 gp gt divrem 3 4x5 46 679854416061557429831102981661718339 0 gp gt factorint 2 128 1 hT 59649589127497217 1 5704689200685129054721 1 Signalons deux
32. u jusqu ce que a soit non nul De plus while teste la condition avant d ex cuter cmd alors que until ex cute d abord cmd avant de tester la condition 5 6 break next Ces deux instructions permettent de sortir de la structure de contr le courante et de remonter au niveau sup rieur Dans le cas de next on avance d une it ration au niveau atteint Ces deux commandes admettent un argument entier qui permet de sp cifier le nombre de niveaux remonter 5 7 Variables locales Toutes les variables d finies sont consid r es comme globales et trait es comme telles dans les fonctions gP gt p 3 h1 3 gp gt f x x p gp gt f 2 2 D gp gt f x t 2 3 gp gt g x xtt gp gt f 5 43 5 Toutefois Putilisation d un nom de variable comme param tre d une fonction ou variable d une boucle cache sa valeur globale Le mot cl my permet de limiter la port e d une variable la fonction courante ou m me la boucle courante Une variable d clar e par my est initialis e O Pour viter cette initialisation utiliser my x x gp gt f x t 2 gp gt t hi t gp gt f 2 t 3 2 la variable globale t a t modifi e gp gt t t h amp t gp gt g x my t t 2 gp gt 8 2 t 18 LE SYST ME PARI GP 5 t la variable globale t n est pas affect e Pour viter les conflits de noms de variables qui provoquent des erreurs rare ment compr he
Download Pdf Manuals
Related Search