Résolution de problèmes d'algèbre linéaire sur des matrices presque creuses

English

Séminaire Modèles et Algorithmes Déterministes: CASYS

11/02/2016 - 09:30 Salle 1 - Tour IRMA

En cryptographie comme en analyse combinatoire, nous sommes couramment confrontés au traitement de systèmes d'équations linéaires dont la majorité des entrées sont nulles, systèmes dont les matrices associées sont alors qualifiées de matrices creuses. Je vous propose dans cet exposé d'élargir l'étude classique aux matrices presque creuses, caractérisées par la concaténation d'une matrice creuse et d'un plus ou moins grand nombre de colonnes denses, disons d. Si y est un vecteur fixé, nous cherchons donc à résoudre le système : A.x = y où A  est une matrice presque creuse, éventuellement rectangulaire, dont la dimension la plus large est notée N.

Isoler les colonnes denses de A permet d'obtenir une complexité asymptotique en O(l N^2) + Otilde((max(d,c))^2 N), avec l le nombre maximum d'entrées non nulles par ligne dans sa partie creuse, et c le nombre de processeurs à disposition. Ceci abaisse alors la complexité actuelle du problème, résolue jusqu'ici par Block Wiedemann en O((l+d) N^2) + Otilde(c^2 N) opérations. Par ailleurs, la comparaison asymptotiques avec les algorithmes classiques utilisés pour les matrices denses, de complexité N^(w), montre la chose suivante : lorsque le nombre de colonnes denses ne dépasse pas N^(w-2-epsilon) (qui n'est pas si petit !), notre algorithme reste le plus performant.

L'étude de ces matrices est motivé par le calcul de logarithmes discrets dans les corps finis de moyenne et grande caractéristiques. En effet, notre algorithme simplifie et accélère la résolution d'une des trois phases du crible par corps de nombres (NFS) qui consiste précisément en la recherche d'un élément non trivial du noyau d'une telle matrice.

Il s'agit d'un travail commun avec Antoine Joux.