Théorie algorithmique des nombres
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Consultez la liste des tâches à accomplir en page de discussion.
La théorie algorithmique des nombres ou théorie calculatoire des nombres est une branche des mathématiques et de l'informatique qui essaie de fournir des solutions concrètes et efficaces à des problèmes calculatoires rencontrés en théorie des nombres.
Exemples
modifierPar exemple, le théorème fondamental de l'arithmétique, qui affirme que tout nombre entier se décompose de manière unique en produit de nombres premiers, donne lieu à l'étude d'algorithmes de factorisation efficace. Un autre exemple est le calcul de PGCD et la variété d'algorithmes inventés dont on trouve quelques exemples dans le second volume de The Art of Computer Programming (§ 4.5.2) de Donald Knuth ; encore plus simplement, l'étude d'algorithmes de multiplication rapide.
Applications
modifierCertains des problèmes abordés par la théorie algorithmique des nombres ont une portée concrète importante, entre autres par la cryptographie qui fait un usage abondant de l'arithmétique : test de primalité, factorisation, logarithme discret…
Références
modifier- (en) Eric Bach (en) et Jeffrey Shallit, Algorithmic Number Theory, vol. 1 : Efficient Algorithms, Cambridge, MA, MIT Press, 1996 (ISBN 978-0-262-02405-1) [lire en ligne]
- (en) Henri Cohen, A Course in Computational Algebraic Number Theory [détail de l’édition]
- (en) Richard Crandall et Carl Pomerance, Prime Numbers: A Computational Perspective, Springer-Verlag, 2001 (ISBN 0-387-94777-9) [lire en ligne]
- (en) Victor Shoup, A Computational Introduction to Number Theory and Algebra, CUP, 2005 (ISBN 978-0-521-85154-1) [lire en ligne]
