Théorie algorithmique des nombres et cryptographie: présentation

Présentation générale

L'apparition des systèmes de chiffrement à clefs publiques de façon générale [DiHe76], et du système de chiffrement RSA en particulier [AdRiSh78], a causé un regain d'intérêt pour la théorie des nombres et en particulier l'arithmétique dans ses aspects calculatoires. Pour répondre à des questions aussi simples que celles concernant la décomposition des nombres en facteurs premiers, il a fallu donner des réponses algorithmiques prenant en compte la faisabilité des calculs ainsi que le temps imparti pour donner une réponse satisfaisante. Cela a provoqué l'essor de la théorie algorithmique des nombres.

Il existe une intéraction très étroite entre les théories mathématiques de haut niveau employées (courbes elliptique, corps de nombres, etc.) et l'utilisation de moyens de calcul nouveaux (machines parallèles, réseaux de stations de travail). Ces deux axes sont représentés au LIX.

Pour en savoir plus

Références du texte :
[AdRiSh78] L. M. Adleman, R. L. Rivest, and A. Shamir. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120--126, 1978.
[DiHe76] W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. on Information Theory, IT-22-6, November 1976.

Références générales :
[Bressoud89] D. Bressoud. Factorization and primality testing. Undergraduate Texts in Mathematics. Springer-Verlag, 1989.
[Cohen93] Henri Cohen. A course in algorithmic algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer--Verlag, 1993.
[Knuth81] D. E. Knuth. The Art of Computer Programming: Seminumerical Algorithms. Addison-Wesley, 2nd edition, 1981.
[Koblitz87b] Neal Koblitz. A course in number theory and cryptography, volume 114 of Graduate Texts in Mathematics. Springer--Verlag, 1987.
[Kranakis1986] Evangelos Kranakis. Primality and cryptography. Wiley-Teubner Series in Computer Science. John Wiley & Sons, 1986.
[Riesel85] Hans Riesel. Prime numbers and computer methods for factorization, volume 57 of Progress in Mathematics. Birkhäuser, 2nd edition, 1985.