Outre la théorie de la complexité algorithmique, la
cryptographie s'appuie sur la théorie des nombres,
en particulier sur les questions liées à
la factorisation des nombres entiers. Le groupe suit de très
près les développements dans ce domaine qui conditionnent la
sécurité de nombreux algorithmes cryptographiques. Il a
participé, en collaboration avec des chercheurs étrangers, à
l'élaboration de diverses techniques de pointe, en
particulier à l'accélération du crible algébrique
(Number Field Sieve), méthode de factorisation des entiers naturels
proposée par Lenstra et Pollard en 1990. Cette méthode,
conçue au départ pour factoriser des nombres spéciaux de la forme
, c petit, est heuristiquement la plus rapide de toutes les
méthodes connues. Cependant, pour des entiers généraux, elle se
heurte à des difficultés pratiques telles que la manipulation
de nombres entiers gigantesques (plusieurs millions de décimales).
Un des chercheurs du groupe ([Cou93]) a
développé des techniques modulaires qui permettent
d'éviter ces manipulations trop coûteuses et qui de plus,
facilitent la parallélisation.
La dernière implémentation de l'algorithme NFS faite
par Arjen Lenstra, a utilisé
ces améliorations et a conduit au dernier record du monde dans ce domaine.
Un réseau est un Z-module discret de R
. Réduire un
réseau, c'est trouver une bonne base du réseau,
formée de vecteurs assez courts et assez orthogonaux. C'est un
problème
largement étudié mais
les solutions classiques
- sauf en petite dimension- ne sont jamais constructives.
Lenstra, Lenstra, Lovàsz, en 1983, ont
obtenu un algorithme polynomial, appelé LLL,
qui trouve une assez bonne base du réseau. En particulier, le
premier vecteur de cette base est suffisamment court pour jouer le
même
rôle que le plus court vecteur du réseau.
L'algorithme LLL, qui utilise l'arithmétique rationnelle pour manipuler de très grands nombres est extrêmement inefficace. Les implantations pratiques qui tournent (par exemple aux Bell Labs, à l'Université de Francfort et au LIENS) substituent à l'arithmétique rationnelle l'arithmétique flottante de la machine. L'analyse théorique qui justifie et contrôle cette substitution est très délicate et a été principalement menée par C. Schnorr. Le GRECC s'est attaché à concevoir un algorithme parallèle de réduction de réseau qui intègre les méthodes numériques de Schorr. Une solution élégante a ainsi pu être proposée ([Jou93b,Jou93a]), qui est l'un des résultats d'une thèse soutenue récemment.
Le groupe a également utilisé l'algorithme LLL, décrit ci-dessus, pour calculer explicitement des objets mathématiques complexes : les revêtements de la sphère ramifiés au dessus de trois points seulement,appelés aussi Dessins d'Enfants. L'étude de ces objets remonte au siècle dernier mais ils ont été remis au goût du jour par <<l'esquisse d'un programme>> rédigée il y a quelques années par Alexandre Grothendieck. Au cours de ce travail, ont été obtenus des résultats sur les propriétés de rationalité de ces revêtements ([Cou94d,Cou94c]).
A partir des dessins, il est possible de
construire explicitement des objets mathématiques ayant
certaines propriétés particulièrement intéressantes. Par exemple
on peut ainsi tenter de résoudre certaines instances du problème de
Galois inverse. C'est ainsi que le GRECC a pu
réaliser la construction et le calcul explicite d'un dessin
correspondant à une extension régulière de 
de groupe de
Galois 
([Gra94]). On connaissait l'existence d'une telle
extension sans en avoir la description. Cela prouve l'intérêt des
techniques de calcul de dessins développées par le groupe
dans [Cou94a] et [CG94a] qui ont permis de
construire explicitement des objets mathématiques impossibles à
traiter par les méthodes usuelles du calcul formel.
C'est René Schoof qui a proposé en 1985 le premier
algorithme polynomial pour le calcul
du nombre de points rationnels sur une courbe elliptique définie
sur un corps fini.
Malheureusement sa méthode restait impraticable et ce sont des
idées d'Elkies et d'Atkin qui on permis d'aboutir à des calculs
explicites au moins dans le cas où le corps est primitif
(
) ou du moins de caractéristique assez grande.
L'application de ces méthodes au calcul
de la cardinalité d'une courbe elliptique sur un corps
de type 
est restée un problème ouvert pendant
quelques années. Or le cas de la caractéristique 2 est le plus
utile dans les applications pratiques (cryptographie en particulier).
Ce problème à été résolu au sein du GRECC en utilisant la géométrie des groupes formels attachés aux courbes elliptiques. Une implémentation réalisée en collaboration avec le laboratoire de l'École Polytechnique a démontré l'efficacité de cette méthode.
À plusieurs reprises, un lien s'est établi entre les recherches du GRECC et la théorie des codes. C'est ainsi que les chercheurs du GRECC ont été amenés à étudier divers problèmes de codes.
De façon inattendue, la seconde famille fournit les meilleurs bornes asymptotiques pour les solutions effectives du <<kissing number problem>>(Placer autant de boules de rayon un que possible au contact d'une boule donnée). ([LS92b,LS94]). Dans le même ordre d'idées, la dérandomisation des algorithmes probabilistes, étudiée en particulier par Alon et al. et Naor et Naor, peut se ramener à des problèmes de théorie des codes. L'utilisation de méthodes de construction de codes algébriques telles que celles de [LS92a] pourrait donc permettre d'améliorer certains résultats.
Enfin, les codes interviennent à plusieurs reprises dans la construction de protocoles basés sur les phénomènes quantiques [BBCS92,BCJL93,CS95,CT95]. On y reviendra plus loin.