Ci-dessous un exemple de comment écrire un premier p (qui est 1 modulo
4) comme une somme de deux carrés, en utilisant pari. Le logiciel pari
est libre (GNU General Public License) et disponible gratuitement sur
le site internet suivant:

                 http://www.parigp-home.de/

Le lecteur constatera que l'utilisation est particulièrement facile,
et mathématiquement rigoureuse. Par exemple, les objets sont typés,
comme on le voit bien avec les entiers modulo p, qu'on peut relever
dans les entiers avec la fonction 'lift'. 

Les commentaires dans les lignes qui suivent commencent par ';', et
ont étés ajoutées après le calcul. 

; La session commence par un message de bienvenue, et quelques
; précisions.


Appele avec : /usr/local/bin/gp -s 10000000 -p 500000 -emacs

                  GP/PARI CALCULATOR Version 2.1.0 (released)
                i686 running linux (ix86 kernel) 32-bit version
                (readline v4.1 enabled, extended help available)

                       Copyright (C) 2000 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and 
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

   realprecision = 28 significant digits
   seriesprecision = 16 significant terms
   format = g0.28

parisize = 10000000, primelimit = 500000

; le 'prompt' de pari est '?'. Le output commence par '%'.
; On commence par chercher le premier p premier après 10^30 qui est 1
; modulo 4. On a de la chance car le premier est bon. 

? p=nextprime(10^30)
%1 = 1000000000000000000000000000057

; Ensuite, on détermine la partie impaire m de p-1. 

? m=(p-1)/4
%2 = 250000000000000000000000000014
? m=m/2
%3 = 125000000000000000000000000007

; On définit a comme étant l'élément 2 de Z/pZ.

? a=Mod(2,p)
%4 = Mod(2, 1000000000000000000000000000057)

; On définit b dans Z/pZ comme étant a^m.  

? b=a^m
%5 = Mod(835456628479332117420647150048, 1000000000000000000000000000057)

; On vérifie si b^2 = -1 dans Z/pZ. C'est le cas. Sinon, on aurait
; fait b=b^2 jusqu'à ce que b^2 = -1. 

? b^2
%6 = Mod(1000000000000000000000000000056, 1000000000000000000000000000057)

; On définit c comme étant un représentant de b dans Z. 

? c=lift(b)
%7 = 835456628479332117420647150048

; On définit la matrice x dont les 4 colonnes forment un système de
; générateurs (en tant que Z-module) de l'idéal de Z[i] engendré par p
; et c-i (la Z-base de Z[i] étant (1,i)).

? x=[p,0,c,1;0,p,-1,c]
%8 = 
[1000000000000000000000000000057 0 835456628479332117420647150048 1]

[0 1000000000000000000000000000057 -1 835456628479332117420647150048]

; Maintenant l'étape la plus compliquée: on appelle la fonction qflll
; qui effectue l'algorithme LLL, avec l'option `flag=4', ce qui donne 
; comme résultat un vecteur de deux matrices, dont la deuxième est une 
; matrice de transformation T telle que x*T (produit de matrices) soit
; une Z-base LLL-réduite du Z-module engendré par les colonnes de
; x. Pour la notion de LLL-réduite le lecteur est référé au livre par
; Henri Cohen cité dans le polycopié du cours. L'idée est que les
; éléments de cette base sont assez orthogonaux, et donc `petits'. 

? y=qflll(x,4)
%9 = [[-835456628479332117420647150048, -697987778070052773254467129865; 1, 0; 1000000000000000000000000000057, 835456628479332117420647150048; 0, 1], [-340822742317508, 762776268894901; 0, 0; 407947858332109, -913005227193276; 0, 0]]

; Comme dit en haut, c'est la deuxième composante de y qui nous
; intéresse. Pour information: la première composante est une base du
; noyau de x. 

? z=y[2]
%10 = 
[-340822742317508 762776268894901]

[0 0]

[407947858332109 -913005227193276]

[0 0]

; Comme dit en haut, z est une matrice de passage. La base LLL-réduite
; qui nous intéresse est le produit x*z.

? u=x*z
%11 = 
[913005227193276 407947858332109]

[-407947858332109 913005227193276]

; Voilà, le calcul est terminé: chaque colonne est un générateur de
; l'idéal de Z[i] engendré par c-i. On vérifie que la somme des deux
; carrés est bien p. 

? u[1,1]^2+u[2,1]^2
%12 = 1000000000000000000000000000057
?