Un ingrédient crucial de nombreuses primitives cryptographiques telles que les protocoles d'échange de clé et les schémas de signature avancés est une action de groupe commutative où la structure du groupe sous-jacent peut être calculée efficacement. SCALLOP fournit une telle action de groupe, basée sur les courbes supersingulières orientées. Nous présentons PEARL-SCALLOP (Parameter Extension Applicable in Real-Life SCALLOP), une variante de SCALLOP qui en change la conception et certains paramètres, améliorant ainsi à la fois l'efficacité et la sécurité et rendant possible la génération de paramètres pour de plus hauts niveaux de sécurité. Dans le cadre de SCALLOP, nos paramètres sont essentiellement optimaux ; l'orientation est donnée par une 2^e-isogénie, où 2^e est approximativement égal au discriminant du groupe de classes. Nous présentons comme important sous-routine un algorithme efficace pour générer des courbes elliptiques supersingulières orientées. Pour mettre en lumière nos améliorations, nous fournissons une implantation preuve-de-concept qui instancie PEARL-SCALLOP à tous les niveaux de sécurité pertinents. Nos temps de calcul sont plus d'un ordre de magnitude plus courts que toute implantation précédente.
Nous développons une nouvelle approche de l'isospectralité des orbivariétés construites par Vignéras. Nous donnons de fins critères suffisants pour la i-isospectralité et l'équivalence en représentations. Ceux-ci nous permettent de produire de très petits exemples exotiques d'orbivariétés isospectrales : des 3-orbivariétés hyperboliques qui sont i-isospectrales pour tout i mais pas équivalentes en représentations, des 3-orbivariétés hyperboliques qui sont 0-isospectrales mais pas 1-isospectrales, et d'autres. En utilisant la même méthode, nous donnons aussi des critères suffisants pour la rationalité des quotients de régulateurs Reg_i(Y_1)^2/Reg_i(Y_2)^2 pour des orbivariétés de Vignéras Y_1, Y_2, parfois alors même qu'elles ne sont pas isospectrales. De plus, nous établissons un lien entre les nombres premiers qui apparaîssent dans ces quotients de régulateurs et auxquels la torsion dans l'homologie de Y_1 et Y_2 peut différer, et les représentations galoisiennes.
Dans cette note, nous présentons une version simplifiée (mais plus lente) Clapoti de Clapotis, dont la description complète apparaîtra ultérieurement. Soit E/F_q une courbe elliptique munie d'une orientation primitive effective par un ordre quadratique R dans End(E). Soit A un idéal inversible de R. Clapoti est un algorithme en temps polynomial randomisé dans O(log Delta_R + log q)^O(1) qui calcule l'action du groupe des classes E→E_A = E/E[A]. Cette note sera remplacée par l'article en préparation.
Le problème Anneau des endomorphismes supersingulier est le suivant : étant donnée une courbe elliptique supersingulière, calculer tous ses endomorphismes. La difficulté présumée de ce problème est une fondation de la cryptographie à base d'isogénies. Le problème Un endomorphisme demande seulement de trouver un endomorphisme non scalaire. Nous prouvons que ces deux problèmes sont équivalents, sous une réduction en temps polynomial probabiliste. Nous prouvons plusieurs conséquences. Premièrement, en supposant le problème Anneau des endomorphismes difficile, la fonction de hachage de Charles-Goren-Lauter résiste aux collisions, et le protocole d'identification SQIsign est sain. Deuxièmement, le problème Anneau des endomorphismes est équivalent au problème de calculer des isogénies arbitraires entre courbes elliptiques supersingulières, un résultat qui était auparavant connu uniquement pour les isogénies de degré friable. Troisièmement, il existe inconditionnellement un algorithme probabiliste résolvant le problème Anneau des endomorphismes en temps O~(sqrt(p)), un résultat qui nécessitait de supposer l'hypothèse de Riemann généralisée avant notre travail. Afin de prouver notre résultat principal, nous introduisons un cadre flexible pour l'étude des graphes d'isogénies avec information supplémentaire. Nous prouvons un théorème de mélange rapide qui est général et facile à utiliser. La preuve de ce résultat passe par une version augmentée de la correspondance de Deuring et la correspondance de Jacquet-Langlands.
Nous décrivons des algorithmes pour représenter et calculer des groupes de caractères de Hecke. Nous utilisons un point de vue idélique et obtenons la totalité de ces caractères, y compris transcendants. Nous montrons également comment isoler les caractères algébriques, qui sont particulièrement intéressants en théorie des nombres. Nous avons implanté ces algorithmes dans Pari/GP, et nous illustrons notre travail par une collection d'exemples qui utilisent notre implantation.
Pour un groupe fini G, nous introduisons une généralisation des relations entre normes dans l'algèbre de groupe Q[G]. Nous donnons des critères nécessaires et suffisants d'existence de telles relations et les appliquons pour obtenir des relations entre les invariants arithmétiques des sous-corps d'un corps de nombres de groupe de Galois G. D'un point de vue algorithmique, nous obtenons des algorithmes exploitant les sous-corps pour le calcul de l'anneau des entiers, des groupes de S-unités et du groupe des classes. Dans les cas du calcul de groupes de S-unités, cette approche donne une réduction polynomiale au problème correspondant dans les sous-corps. Nous calculons des groupes de classes de grands corps de nombres sous GRH, et de nouvelles valeurs inconditionnelles de nombres de classes de corps cyclotomiques. Le script GP est disponible ici.
Soit k un corps de caractéristique suffisamment grande. Nous présentons un algorithme qui résout le problème suivant : étant données deux courbes de genre 2 sur k dont les jacobiennes sont isogènes, calculer une isogénie explicite entre elles. Cette isogénie peut être une l-isogénie ou, dans le cas de la multiplication réelle, une isogénie à noyau cyclique. L'algorithme utilise les équations modulaires pour ces types d'isogénies.
Lenstra et Guruswami ont décrit des analogues sur les corps de nombres des codes de géométrie algébrique de Goppa. Récemment, Maire et Oggier ont généralisé ces constructions à d'autres groupes arithmétiques : aux groupes d'unités dans les corps de nombres et aux ordres dans les algèbres à division ; il et elle ont suggéré l'utilisation de groupes d'unités dans les algèbres de quaternions mais n'ont pas pu analyser complètement les codes qui en résultent. Nous prouvons que la construction utilisant des groupes d'unités non commutatifs produit des familles de codes asymptotiquement bons pour la métrique somme-rang à partir d'algèbres à division de degré arbitraire, et nous estimons la taille de l'alphabet en fonction du degré.
Lorsque M est une variété munie d'une action d'un groupe G, le groupe d'homologie H_1(M,Q) est naturellement un Q[G]-module, où Q[G] désigne l'anneau de groupe rationnel. Nous prouvons que pour tout groupe fini G et pour tout Q[G]-module V, il existe une 3-variété fermée hyperbolique munie d'une action libre de G telle que le Q[G]-module H_1(M,Q) est isomorphe à V. Nous donnons une application à la géométrie spectrale: pour tout ensemble fini P de nombres premiers, il existe des 3-variétés hyperboliques N et N' qui sont fortement isospectrales mais telles que pour tout p dans P, les sous-groupes p-primaires de la torsion dans H_1(N,Q) et H_1(N',Q) sont d'ordre différents. Nous montrons également que, dans un certain sens précis, l'homologie rationnelle des 3-variétés riemanniennes orientées munies d'une G-action ne "sait" rien sur la structure des points fixes sous G, au contraire du cas de la dimension 2. Les principales techniques géométriques sont la chirurgie de Dehn et, pour l'application spectrale, la formule de Cheeger-Mueller, mais nous utilisons également des outils de différentes branches de l'algèbre, notamment les constantes de régulateurs, un outil de théorie des représentations qui a été développé à l'origine dans le contexte des courbes elliptiques.
Étant donné un groupe fini G, un G-revêtement de variétés riemanniennes fermées, et une « G-relation », une construction de Sunada produit deux variétés M_1, M_2 fortement isospectrales. De telles variétés ont la même dimension et le même volume, et leurs groupes d'homologie sur Q sont isomorphes. Dans cet article, nous nous intéressons à la relation entre leurs groupes d'homologie sur Z. Le théorème de Cheeger-Mueller implique qu'un certain produit d'ordres de torsion dans l'homologie et de régulateurs doit être identique pour M_1 et M_2. Nous exhibons un lien entre la torsion dans l'homologie de M_1 et M_2 d'une part, et la structure de G-module de l'homologie sur Z de la variété revêtant M_1 et M_2 d'autre part, en interprétant les quotients Reg_i(M_1)/Reg_i(M_2) en termes de théorie des représentations. De plus, nous prouvons que la torsion p-primaire dans l'homologie de M_1 est isomorphe à celle de M_2 pour tout p ne divisant pas #G. Pour tout nombre premier p ≤ 71, nous produisons un exemple de paire de 3-variétés arithmétiques hyperboliques fortement isospectrales pour lesquelles la p-torsion dans l'homologie diffère.
Ethan et Alexander établissent des formules de dimension générales pour la seconde page de la suite spectrale équivariante des groupes SL_2 sur les entiers quadratiques imaginaires agisant sur leur espace symétrique associé. Au passage, ils étendent la technique de réduction du sous-complexe de torsion à des cas où le noyau de l'action est non trivial. En utilisant les suites spectrales équivariante et de Lyndon-Hochschild-Serre, ils analysent les différentielles de la seconde page et montrent comment obtenir les anneaux de cohomologie mod 2 de ces groupes à partir de cette information. Dans l'appendice, je fournis des résultats numériques correspondants en utilisant mon logiciel Kleinian Groups.
Dans un corps de nombres, le problème de l'idéal principal consiste à décider si un idéal est principal, et le cas échéant à en trouver un générateur. Ce problème possède de nombreuses applications en théorie algorithmique des nombres. Dans une algèbre de quaternions indéfinie, le problème de décision se ramène au même problème dans le corps de base. Trouver un générateur est difficile, et je présente un algorithme sous-exponentiel pour cette tâche.
Un groupe kleinéen arithmétique est un réseau arithmétique de PSL_2(C). Je présente un algorithme qui, étant donné un tel groupe Γ, calcule un domaine fondamental et une présentation finie pour Γ avec un isomorphisme calculable. C'est une amélioration de l'algorithme de mon Master. Le paquet Magma est disponible ici.
Dans cet article, Fabrice introduit une généralisation de la notion de relations de norme dans l'algèbre de groupe Q[G], où G est un groupe fini. Il donne des propriétés de ces relations et il les utilise pour obtenir des relations entre les groupes des S-unités de différents sous-corps de la même extension Galoisienne de Q, de groupe de Galois G. Puis il en déduit un algorithme pour calculer le groupe des classes de certains corps de nombres en réduisant le problème à d'autres corps de nombres de plus petit degrés. Enfin, il calcule le groupe des classes de certains grands corps de nombres.
Soit F un polynôme ou une fraction rationnelle univariée de degré d définie sur un corps de nombres. Dans cet article, Jean donne des bornes supérieures sur la hauteur de Weil absolue logarithmique de F en termes de la hauteur de ses valeurs en de petits entiers : il passe en revue des bornes bien connues obtenues à partir d'algorithmes d'interpolation étant données des valeurs en d+1 (resp. 2d+1) points, et obtient des résultats plus fins en considérant un plus grand nombre de points d'évaluation.
Dans cet article, Jean décrit des algorithmes pour évaluer efficacement les polynômes modulaires en genre 2 de type Siegel ou Hilbert sur les corps de nombres, en utilisant des approximations complexes. Sous des heuristiques liées au calcul de fonctions thêta en temps quasi-linéaire, la sortie est prouvablement correcte. Ses algorithmes s'appliquent aussi sur des corps finis par relèvement.
Les algorithmes quasi-linéaires existants pour calculer les constantes thêta en genre 2 utilisent une suite de Borchardt, un analogue de la moyenne arithmético-géométrique pour quatre nombres complexes. Dans cet article, Jean montre que ces suites de Borchardt sont données uniquement par de bons choix de racines carrées, comme dans le cas du genre 1. Cela supprime les indéterminations de signes dans l'algorithme sans avoir recours à une intégration numérique.
Dans cet article, Jean définit les équations modulaires dans le contexte des variétés de Shimura PEL comme des équations décrivant les correspondances de Hecke, et prove des bornes de degré et de hauteur pour ces équations. En particulier, il obtient des bornes de degré fines pour les équations modulaires de type Siegel et Hilbert pour les surfaces abéliennes.
Méthodes explicites pour les groupes arithmétiques. [ HAL | mémoire (anglais) ]
Thèse réalisée sous la direction de Karim Belabas et Andreas Enge. Voici le résumé de la thèse.
Computing fundamental domains for arithmetic Kleinian groups. [ HAL | mémoire (anglais) ]
Mémoire réalisé sous la direction de John Voight.
L'équation de Pell-Fermat non commutative. [ texte ]
Higher-dimensional modular equations, applications to isogeny computations and point counting, par Jean Kieffer. [ HAL (anglais) ]
Thèse co-encadrée avec Damien Robert.
Nous définissions un schéma de comparaison et d'étiquetage des idéaux entiers dans les corps de nombres, incluant les idéaux premiers comme cas particulier. L'ordre que nous définissons ne dépend que du choix d'un polynôme de définition entier irréductible unitaire pour chaque corps K, et nous commençons par définir pour chaque corps son unique polynôme de définition réduit, d'après Belabas. Nous définissons un ordre total sur l'ensemble des idéaux premiers de K et l'étendons ensuite en un ordre total sur l'ensemble de tous les idéaux entiers non nuls de K. Cet ordre nous permet de donner à chaque idéal une unique étiquette de la forme N.i, où N est sa norme et i est l'indice de l'idéal dans la liste ordonnée de tous les idéaux de norme N. Notre schéma d'étiquetage possède plusieurs propriétés agréables : pour une norme donnée, les idéaux premiers apparaîssent en premier, et étant donnée la factorisation de la norme, la bijection entre les idéaux de norme N et les étiquettes est calculable en temps polynomial. Notre motivation est d'avoir une manière concise et bien définie de trier et étiqueter les idéaux pour utilisation dans des bases de données telles que la LMFDB. Nous avons implanté des algorithmes qui réalisent ce schéma en Sage, Magma et Pari. Le code est disponible sur Github.
Hardness of isogeny problems and equidistribution, au MPIM (Bonn, Allemagne) le 05/12/2024. [ notes (anglais) ]
Equidistribution of curves with extra structure, au séminaire CANARI (Bordeaux) le 01/10/2024. [ notes (anglais) ]
Isospectrality, regulators and torsion of Vignéras manifolds, au MFO (Oberwolfach, Allemagne) le 02/09/2024. [ slides (anglais) ]
Computing class groups using norm relations, au CIRM (Luminy) le 03/03/2023. [ slides (anglais) ]
Computing groups of Hecke characters, à ANTS XV (Bristol, Royaume-Uni) le 08/08/2022. [ slides (anglais) | vidéo (anglais) ]
Algorithms for the cohomology of compact arithmetic manifolds, au séminaire Cogent (en ligne) le 30/05/2022. [ slides (anglais) ]
Torsion homology and regulators of Vignéras isospectral manifolds, à la conférence Arithmetic Groups and 3-Manifolds (Bonn, Allemagne) le 17/05/2022. [ slides (anglais) ]
Torsion dans l'homologie des variétés isospectrales de Vignéras et opérateurs de Hecke, au séminaire de théorie des nombres de Besançon le 12/04/2022. [ notes ]
Norm relations and class group computations, au séminaire LFANT (Bordeaux) le 23/11/2021. [ notes (anglais) ]
Algorithmes pour la topologie des variétés arithmétiques compactes et les opérateurs de Hecke, à l'Institut Fourier (Grenoble) le 01/02/2018 au séminaire de théorie des nombres. [ notes ]
Torsion dans l'homologie des groupes kleinéens arithmétiques, à l'IRMAR (Rennes) le 11/12/2015, au Séminaire de géométrie et algèbre effectives. [ slides ]
Isospectrality, regulators and special value formulas, à Brown University, Providence (Rhode Island, États-Unis) le 16/11/2015, à l'ICERM peer-to-peer seminar. [ slides (anglais) ]
Calcul de formes modulaires de Klein, à Clermont-Ferrand le 9/12/2014, au groupe de travail de théorie des nombres. [ slides ]
An algorithm for the principal ideal problem in indefinite quaternion algebras à GyeongJu (Corée) le 11/08/2014, Algorithmic Number Theory Symposium XI. [ slides (anglais) ]