oui oui les nombres p_adiques je connais bien attendez je demande a mon fils de 8 ans c'est dans le programme de primaire
En 1999, Satoh a introduit les m?thodes p-adiques (en particulier le rel?vement canonique d'une courbe elliptique) dans le calcul de la cardinalit?. Alors que les m?thodes ? la Schoof-Elkies-Atkin ont une complexit? heuristique (avec de la multiplication rapide) en O(n^{4+epsilon}), l'algorithme annonc? par Satoh atteint une complexit? th?orique d?terministe prouv?e en O(n^{3+epsilon}). L'entier n d?signe ici le degr? de l'extension d?finissant le corps fini. Le coup d'envoi de la mise en pratique de cet algorithme a ?t? donn? par Fouquet-Gaudry-Harley qui ont propos? une extension au cas de p=2. Ce cas n'?tait pas trait? dans l'article de Satoh bien qu'ayant le plus d'int?r?t pratique (cette extension a ?t? effectu?e ind?pendamment par Skjernaa). Des exp?riences pratiques ont permis d'une part de pulv?riser les pr?c?dents records (passant de 2000 ? 8000 bits) et d'autre part de gagner un ordre de grandeur sur les temps de calcul pour les tailles utiles en cryptographie.
Des am?liorations se sont succ?d?es et les diff?rentes alternatives sur le march? actuellement incluent l'algorithme de Vercauteren et al. qui r?duit la complexit? spatiale ? O(n^2), la m?thode AGM invent?e par Mestre et d?velopp?e par Harley et Gaudry qui pr?sente les m?mes avantages tout en am?liorant les constantes, et derni?rement la m?thode de Satoh-Skjernaa-Taguchi (SST) qui am?liore la complexit? th?orique au prix de quelques pr?calculs. De nouveaux progr?s sont encore en cours ou ? venir (voir le r?cent record de Harley ? 32000 bits).
Les m?thodes p-adiques s'?tendent relativement bien aux courbes autres qu'elliptiques. Tout d'abord l'algorithme AGM de Mestre s'?tend aux courbes de genre 2 et fonctionne tr?s bien en pratique (plus lentement d'un facteur 3 environ par rapport ? une courbe elliptique de m?me taille). Par ailleurs, Kedlaya a introduit une nouvelle approche, bas?e non plus sur le rel?vement canonique, mais sur la cohomologie de Monsky-Washnitzer. Son algorithme fonctionne pour les courbes hyperelliptiques en caract?ristique diff?rente de 2. Gaudry et G?rel ont ensuite implant? cet algorithme et l'ont ?tendu aux courbes superelliptiques, montrant ainsi que les tailles cryptographiques sont atteignables pour cette classe de courbes. Vercauteren et Denef ont trouv? une adaptation de l'algorithme pour traiter le cas hyperelliptique en caract?ristique 2. L? encore des implantations prototypes ont d?montr? la faisabilit? en vraie grandeur. Citons pour finir les travaux de Lauder et Wan qui en rendant effective la preuve de Dwork de la rationalit? de la fonction Zeta ont fourni un algorithme polynomial qu'ils ont ensuite adapt? au cas particulier des courbes hyperelliptiques.
merci fiston du va surement eclairer notre boulet de build car tu sais les suisses on du retard au nivo scolaire
