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

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 sur les entiers.
La forme normale de Smith (SNF) des matrices d'entiers est un outil fondamental en algèbre linéaire exacte, avec de nombreuses applications en analyse diophantienne, en combinatoire et pour la détermination de la structure canonique des groupes abéliens finis. Cette dernière a trouvé des applications récentes en cryptographie, où plusieurs protocoles avancés reposent sur la difficulté de calculer la structure du groupe de classes d'un corps de nombres. Les cryptanalyses les plus avancées, qui évaluent le choix de la taille des paramètres pour ces protocoles, manquent d'algorithmes optimisés récents et d'implémentations HPC correspondantes — un domaine où l'algèbre linéaire entière avec des matrices creuses joue un rôle crucial.

L'objectif de cette thèse est double :
1. Fournir des implémentations de haute performance des algorithmes de pointe pour le calcul de la forme normale de Smith de matrices creuses d'entiers, et adapter ces solutions au cas spécifique de la cryptanalyse des groupes de classes.
2. Développer de nouveaux algorithmes présentant soit une meilleure complexité asymptotique, soit permettant des améliorations pratiques significatives, telles qu'une exploitation optimisée des hiérarchies de mémoire cache, du parallélisme à haut niveau ou des architectures orientées GPU.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Linear algebra is a major tool across several domains in computer science and mathematics. It is frequently the case that it becomes the primary computational bottleneck in realistic applications aiming to deal with very large matrices. For instance, this is a major challenge in algebraic cryptanalysis, e.g. integer factorization or discrete logarithm problems, where matrices can reach dimensions of several billions while featuring very few non-zero elements.
While significant efforts have targeted sparse matrices with floating-point numbers or exact arithmetic over finite fields in cryptography—culminating in highly practical algorithms and optimized implementations leveraging High-Performance Computing (HPC) infrastructures—the landscape remains considerably less clear for sparse matrices over the integers.

The Smith Normal Form (SNF) of integer matrices is a fundamental tool in exact linear algebra with numerous applications in Diophantine analysis, combinatorics, and for determining the canonical structure of finite Abelian groups. The latter has found recent applications in cryptography, where several advanced protocols rely on the hardness of computing the structure of the class group of a number field. The most advanced cryptanalysis that
assess the choice of parameter sizes for these protocols lack recent optimized algorithms and corresponding HPC implementations, a domain where integer linear algebra with sparse matrices plays a crucial role.

The goal of this thesis is two-fold:
1. Provide high-performance implementations of state-of-the-art algorithms for computing the Smith normal form of sparse integer matrices, and adapt these solutions to the specific case of class group cryptanalysis.
2. Derive new algorithms either exhibiting better asymptotic complexity or allowing significant practical improvements, such as enhanced exploitation of cache hierarchies, high-level parallelism, or GPU-oriented architectures.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/2026

Autre financement public

ANR Financement d'Agences de financement de la recherche

Université de Montpellier

166 I2S - Information, Structures, Systèmes

Profil académique : Le candidat idéal devra être titulaire d'un Master (ou diplôme équivalent) en informatique, en mathématiques calculatoires ou dans un domaine étroitement lié. Compétences théoriques : De solides bases en algèbre linéaire et en calcul formel sont indispensables, ainsi qu'un intérêt prononcé pour la conception d'algorithmes et la théorie de la complexité. Compétences techniques : Une excellente maîtrise de la programmation en C/C++ est requise. Une expérience préalable avec les architectures parallèles de calcul haute performance (HPC) ou en optimisation est fortement souhaitable.
Academic Background: The ideal candidate will hold an MSc (or equivalent) in Computer Science, Computational Mathematics, or a closely related field. Theoretical Expertise: A strong foundation in linear algebra and computer algebra is essential, alongside a demonstrated interest in algorithm design and complexity theory. Technical Skills: Proficiency in C/C++ programming is required. Prior experience with High- Performance Computing (HPC) parallel architectures or optimization is highly desirable.