Algèbre linéaire creuse pour le logarithme discret

Présentation du problème Les systèmes d’équations linéaires que nous allons étudier ici sont issus des algorithmes de calcul d’index. Pour une description plus détaillée de ces algorithmes, le lecteur peut se référer au chapitre 1. Dans ces algorithmes, l’étape de crible fournit des relations entre les logarithmes de certains éléments. Par la suite, l’étape de filtrage en quelque sorte « nettoie » et « prépare » le système à résoudre. Nous avons besoin de résoudre ce système pour pouvoir calculer dans l’étape de logarithme individuel le logarithme discret de n’importe quel élément du corps, à partir des logarithmes déjà connus. Nous calculons le logarithme discret dans un sous-groupe multiplicatif d’un corps fini Fq. L’ordre de ce sous-groupe est premier et est noté `. On rappelle que ` est un diviseur de q − 1 (voir sous-section 1.4.5). Les entrées de la phase d’algèbre linéaire sont : — le nombre premier ` ; — une matrice carrée et singulière A, à N lignes et colonnes et définie dans le corps fini (Z/`Z). Nous cherchons un élément non trivial du noyau de la matrice, autrement dit une solution de l’équation Aw mod ` = 0 (3.1) Nous allons considérer des matrices issues des calculs avec les algorithmes FFS et NFS. Les propriétés que nous allons décrire peuvent ne pas être valides pour des matrices issues d’autres algorithmes de calcul d’index. Fabrication de la matrice par l’étape de filtrage L’étape de filtrage est une étape de pré-calcul qui permet de réduire la taille de la matrice. La description que nous fournissons du filtrage est basée sur les travaux [Cav02, chap. 3] et [Bou13]. À l’entrée du filtrage, la matrice est très grande et très creuse (environ 20 coefficients non nuls par ligne). La matrice n’est généralement pas carrée ; elle contient plus de lignes que de colonnes (c’est-à-dire plus d’équations que d’inconnues). L’objectif du filtrage est de diminuer la taille de la matrice sans trop la densifier ; la densité finale correspond à quelques centaines de coefficients non nuls par ligne. On désire généralement pour la suite de l’algèbre linéaire une matrice carrée. Cette étape de pré-calcul tend à augmenter le nombre moyen de coefficients non nuls par ligne, mais permet de diminuer la taille de la matrice. La diminution de la taille est importante pour la résolution effective du système linéaire. D’une part, elle réduit la quantité de mémoire nécessaire à la représentation et au traitement de la matrice. D’autre part, elle diminue le coût de la résolution effective, sachant que les algorithmes de résolution effective, comme nous allons le voir dans la prochaine section, ont une complexité au moins quadratique, si ce n’est cubique, en la taille de la matrice. Au fur et à mesure que le filtrage agit sur la matrice, le coût estimé de la résolution effective diminue. Le filtrage est arrêté lorsque le coût recommence à augmenter. Il existe une autre méthode pour diminuer la taille de la matrice, qui est celle de l’élimination gaussienne structurée (SGE pour Structured Gaussian Elimination) [LO90, PS92]. Les approches SGE et celle du filtrage sont similaires ; elles se distinguent de par la stratégie et les critères qu’elles emploient pour le choix des lignes à combiner ou à supprimer. Dans la table 3.1, nous illustrons l’évolution de la taille de la matrice pendant le filtrage avec deux exemples de matrices issues de calculs concrets de logarithme discret ; une matrice FFS qui correspond à la résolution du logarithme discret dans F2 809 et une matrice NFS issue de la résolution du logarithme discret dans un corps premier Fp155 , où p155 est un nombre premier de 155 chiffres décimaux. 

Caractéristiques des entrées

Le nombre ` est un « grand » nombre premier, de l’ordre de quelques centaines de bits. D’un point de vue cryptographique, le nombre ` doit être suffisamment grand de sorte à ce que le sous-groupe correspondant résiste à des attaques de type Pollard rho (voir sous-section 1.4.1 pour de plus amples explications). La matrice A est grande. Sa dimension N peut aller de centaines de milliers à des dizaines de millions de lignes, si on se réfère aux calculs récents de logarithme discret. La matrice est creuse. Une analyse asymptotique donne une densité indicative de O 

Nature des coefficients

La matrice A est définie sur le corps (Z/`Z). Toutefois, la majorité des coefficients sont « petits », dans le sens où ils peuvent être représentés par un entier de petite taille, tenant dans un mot machine (éventuellement signé). Ces coefficients correspondent à des exposants dans les relations trouvées dans la phase de crible. Pour les matrices issues d’un calcul FFS, tous les coefficients sont « petits ». Les courbes de la figure 3.1 montrent la répartition des valeurs des coefficients dans la matrice-exemple de FFS pour F2 809 . En abscisse, on représente les valeurs des coefficients et en ordonnée le nombre d’apparition dans la matrice. Tous les coefficients sont compris entre −35 et 36. En échelle linéaire, il y a deux grands pics qui correspondent aux valeurs −1 et 1 et deux autres pics moins importants pour les valeurs −2 et 2. En effet, 92.7% des coefficients sont des ±1 et 4.5% des coefficients sont des ±2. Quand nous passons en échelle logarithmique, nous observons une répartition quasi triangulaire que nous n’expliquons pas ici ; l’explication pourrait être trouvée avec une étude statistique de l’étape de filtrage.