Thèse Algorithmes Efficaces pour le Calcul de Forme de Smith de Matrices Creuses et Application à la Cryptanalyse Algébrique H/F - Doctorat.Gouv.Fr

Établissement : Université de Montpellier École doctorale : I2S - Information, Structures, Systèmes Laboratoire de recherche : Laboratoire d'Informatique, de Robotique et de Micro-électronique de Montpellier Direction de la thèse : Pascal GIORGI ORCID 0000000204895134 Début de la thèse : 2026-10-01 Date limite de candidature : 2026-06-30T23:59:59 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. 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 de formaliser de nouveaux algorithmes plus efficace pour établir les paramètres de sécurité de protocoles cryptographique s'appuyant sur le calcul de groupe de classe de corps de nombre.

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.

• C++
• Programmation
• Calcul haute performance