logomagistere entetesite logomagistere
 
Accueil
Présentation
Les enseignements
Les mémoires
  Première année
    Organisation
    Exemples
  Troisième année
Les stages
Liens
Etude de la primalité motivée par le besoin de nombres premiers dans le chiffrement RSA

Auteure : Marie-Aude STEINEUR,
Responsable : Jean-François BOUTOT. Professeur à l’UFR de Maths-Info
Année : 2005 - 2006


De quoi ça parle ?

Depuis leur apparition, l’arithmétique et l’algèbre mêlent de façon confuse les calculs théoriquement possibles et effectivement réalisables. Ce n’est que depuis le développement des théories de l’informatique et de la complexité que des énoncés précis ont pu être formulés et illustrés par d’impressionnantes applications.
Ainsi la sécurité des transactions interbancaires repose-t-elle sur la difficulté de la décomposition des grands nombres en facteurs premiers via des systèmes cryptographiques tels que le chiffrement RSA. Pour construire ces grands nombres, il faut générer de grands nombres premiers. S’il est théoriquement possible de vérifier la primalité d’un entier quelconque, ce n’est pas toujours techniquement réalisable. Ainsi les différents algorithmes efficaces testant la primalité sont-ils probabiliste : de nos jours il est courant d’utiliser des entiers ”premiers avec une très forte probabilité”. Mais un nouvel espoir apparaît avec l’algorithme d’Agrawal, Kayal et Saxena : c’est le premier a avoir un temps de calcul qui croit de façon polynomiale avec la taille de l’entier à tester.

Nous étudierons donc dans une première partie le chiffrement RSA comme exemple pour comprendre comment sont impliqués les nombres premiers dans la cryptographie.
Nous nous attarderons également sur la notion de complexité, utile pour comparer les différents algorithmes. Dans une seconde partie, nous nous intéresserons a certaines caractéristiquesdes nombre premiers qui nous amèneront aux algorithmes classiques de primalité. La dernière partie sera consacrée à l’algorithme d’Agrawal, Kayal et Saxena.


Le mémoire en version intégrale

Vous pouvez télécharger ce mémoire ici :

PDF - 1.1 Mo
Mémoire de Marie-Aude Steineur

 
Nous contacter
SPIP