Les nombres premiers sont redevenus un sujet fort à la mode. D'abord, ils sont un des thèmes mathématiques facilement compréhensibles par le grand public. Ensuite, les progrès récents des arithméticiens, à commencer par la preuve du Grand Théorème de Fermat par Wiles en 1996, ont attiré l'attention. Enfin, et surtout, de vieilles recherches datant du XVIIè s. ont trouvé récemment des applications concrètes dans l'industrie, grâce à la cryptographie et particulièrement à l'algorithme RSA. Aujourd'hui, des banques, des Etats fabriquent quotidiennement de très grands nombres premiers, tandis que des services secrets ou des hackers s'ingénient à faire l'opération inverse, c'est-à-dire à factoriser des entiers en produits de facteurs premiers.

  On comprend donc bien qu'il est très important de disposer des meilleurs algorithmes à la fois pour tester la primalité et pour factoriser. Ce dossier est consacré au premier problème, à la suite de la découverte d'un nouvel algorithme à l'été 2002 par 3 mathématiciens indiens : Agrawal, Kayal et Saxena.

  Il nous faut avant de commencer donner quelques rudiments de la théorie de la complexité. Un algorithme est dit polynômial en temps s'il existe un polynôme P tel que, en appliquant l'algorithme à une entrée de taille k, l'algorithme effectue moins de P(k) opérations élémentaires (comme ajouter deux nombres, les multiplier ou les comparer). Prenons par exemple un algorithme de test de primalité : son entrée est un entier n, la taille de cet entier est son nombre de chiffres, et vaut un multiple de log n. Un algorithme de test de primalité est donc polynômial si, prenant un entier n, il peut affirmer si n est premier ou composé en effectuant moins de C(log n)^r opérations, où C et r sont des constantes.

  Avant l'été 2002, on ne savait pas s'il existait un test de primalité en temps polynômial, même si on avait de bonnes raisons de le penser. Agrawal, Kayal et Saxena ont donné dans leur article effectivement un tel test de primalité. Nous nous proposons dans ce dossier d'étudier les différents tests de primalité, et leurs conséquences pratiques et théoriques.

Version imprimable