La cryptographie est devenue indispensable afin de garantir la sécurité et l'intégrité des données transitant dans les réseaux de communication modernes. Ces deux dernières décennies, des cryptosystèmes très efficaces, sûr et riches en fonctionnalités ont été construits à partir de variétés abéliennes définies sur des corps finis. Cette thèse contribue à certains aspects algorithmiques des variétés abéliennes ordinaires touchant à leurs anneaux d'endomorphismes. Cette structure joue un rôle capital dans la construction de variétés abéliennes ayant de bonnes propriétés. Par exemple, les couplages ont récemment permis de créer de nombreuses primitives cryptographiques avancées ; construire des variétés abéliennes munies de couplages efficaces nécessite de choisir des anneaux d'endomorphismes convenables, et nous montrons qu'un plus grand nombre de tels anneaux peut être utilisé qu'on ne pourrait croire. Nous nous penchons aussi le problème inverse qu'est celui du calcul de l'anneau d'endomorphisme d'une variété abélienne donnée, et qui possède en outre plusieurs applications pratiques. Précédemment, les meilleures méthodes ne résolvaient ce problème qu'en temps exponentiel ; nous concevons ici plusieurs algorithmes de complexité sous-exponentielle pour le résoudre dans le cas ordinaire. Pour les courbes elliptiques, nous algorithmes sont très efficaces, ce que nous démontrons en attaquant des problèmes de grande taille, insolvables jusqu'à ce jour. De plus, nous bornons rigoureusement la complexité de notre algorithme sous l'hypothèse de Riemann étendue. En tant que sous-routine alternative, nous nous considérons aussi une généralisation du problème du sac à dos dans les groupes finis, et montrons comment il peut être résolu en utilisant peu de mémoire. Enfin, nous généralisons notre méthode aux variétés abélienne de dimension supérieure, ce qui nécessite davantage d'hypothèses heuristiques. Concrètement, nous développons une bibliothèque qui permet d'évaluer des isogénies entre variétés abéliennes ; en utilisant cet outil important dans notre algorithme, nous appliquons notre méthode généralisée à des exemples illustratifs et de tailles jusqu'à présent inatteignables.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00609211 |
| Date | 14 July 2011 |
| Creators | Bisson, Gaetan |
| Publisher | Institut National Polytechnique de Lorraine - INPL |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds