SMF

Exposé Bourbaki 917 : La primalité en temps polynomial

Exposé Bourbaki 917 : Primality in polynomial time

François MORAIN
Exposé Bourbaki 917 : La primalité en temps polynomial
  • Année : 2004
  • Tome : 294
  • Format : Électronique
  • Langue de l'ouvrage :
    Français
  • Class. Math. : 11A41, 11Y11, 11Y16
  • Pages : 205-230
  • DOI : 10.24033/ast.630

Le problème de la primalité est l'un des problèmes les plus simples et les plus anciens de la théorie des nombres. À la fin des années 1970, Adleman, Pomerance et Rumely ont donné le premier algorithme de primalité déterministe, dont le temps de calcul était presque polynomial. Il a fallu 20 années supplémentaires pour qu'Agrawal, Kayal et Saxena donnent un algorithme déterministe de temps de calcul polynomial. L'exposé présentera ces travaux, et il fera également le point sur les différents autres algorithmes inventés dans cette période.

Primality is one of the simplest and oldest problems in number theory. At the end of the seventies, Adleman, Pomerance and Rumely have designed the first deterministic primality proving algorithm, whose running time was quasi polynomial. Twenty years later, Agrawal, Kayal and Saxena gave the first algorithm running in polynomial time. The talk will present all these works, and will also include the description of some of the primality algorithms invented during this period.

Primalité, sommes de Jacobi, courbes elliptiques, courbes hyperelliptiques, multiplication complexe, corps finis
Primality proving, Jacobi sums, elliptic curves, hyperelliptic curves, complex multiplication, finite fields
Des problèmes avec le téléchargement?Des problèmes avec le téléchargement?
Informez-nous de tout problème que vous avez...