Algorithmes efficaces pour le calcul de forme de Smith de matrices creuses, et application à la cryptanalyse algébrique // Efficient algorithms for Smith normal form of sparse matrices, and applications to crypt- analysis

Topic description

L'algèbre linéaire est un outil majeur dans plusieurs domaines de l'informatique et des mathématiques. Il arrive fréquemment qu'elle devienne le principal goulot d'étranglement informatique dans des applications réalistes visant à traiter des matrices de très grande taille. C'est par exemple un défi majeur en cryptanalyse algébrique — comme pour les problèmes de factorisation d'entiers ou du logarithme discret — où les matrices peuvent atteindre des dimensions de plusieurs milliards de lignes et de colonnes, tout en comportant très peu d'éléments non nuls.

Alors que des efforts considérables ont été déployés pour cibler les matrices creuses à virgule flottante ou en arithmétique exacte sur les corps finis en cryptographie — aboutissant à des algorithmes hautement pratiques et à des implémentations optimisées exploitant les infrastructures de calcul haute performance (HPC) —, le paysage reste beaucoup moins clair pour les matrices creuses s...