Jeudi 25 juin 2015 à 10h30 en salle C46
Cécile Pierrot (LIP6, UMPC)
Titre : Algèbre linéaire dense ou creuse ? - Algèbre linéaire presque creuse !
Résumé :
Si l'algèbre linéaire, comme souvent, agit dans les soubassements de la cryptographie, la nature même des équations que l'on rencontre dans notre domaine présente en revanche quelques spécificités. Ainsi sommes-nous 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.
Remarques : Travail commun avec Antoine Joux.