2017, un nombre premier?

Nous entreprenons l’année 2017. Ce nombre a une propriété remarquable: c’est un nombre premier. Ces nombres sont loin d’être aussi banals qu’ils n’y paraissent: ils sont par exemple très importants en cryptographie. C’est grâce à eux que l’on peut effectuer des transactions bancaires en ligne de façon sécuritaire et transmettre d’autres informations sensibles.

Comment fait-on pour vérifier si un grand nombre est premier ou non? La méthode qui nous vient immédiatement à l’esprit consiste à diviser par tous les nombres inférieurs à la valeur à tester, mais cela demande beaucoup de temps. Il y a une autre méthode plus efficace qui permet non seulement de vérifier si un nombre est premier, mais aussi de trouver tous les nombres premiers inférieurs: le crible d’Ératosthène. On fait la liste de tous les entiers supérieurs à un et inférieurs ou égaux à la valeur à vérifier. On commence avec deux. On garde deux comme nombre premier, puis on barre tous ses multiples. Ensuite, on prend le prochain nombre qui n’est pas barré (trois), on le garde comme nombre premier et on barre tous ses multiples. On répète ainsi le procédé jusqu’au bout de la liste. On peut remarquer qu’il suffit de barrer à partir du carré d’un nombre premier trouvé, car les multiples inférieurs au carré d’un nombre sont des multiples d’un nombre qui a déjà été choisi. Par exemple, si on prend 5, alors 5x2, 5x3, 5x4 sont des multiples de 2, 3 et 4, et ils ont donc déjà été barrés.

En pratique, toutefois, ces méthodes sont inefficaces, car on utilise des nombres qui peuvent contenir des centaines de chiffres. Même pour un ordinateur, ce serait trop long à calculer. Il existe une autre méthode : le test de primalité de Fermat, basé sur le petit théorème de Fermat. Pour expliquer ce théorème, on aura besoin de la notion de reste de la division, que l’on devrait avoir vue à l’école primaire. Si, par exemple, on a six pointes de tourtière que l’on veut diviser en quatre parts égales, chacun aura une pointe (le quotient) et il restera deux pointes de tourtière (le reste). Le petit théorème de Fermat nous dit que si un nombre p est premier, différent de 2, alors le reste de la division de 2p-1 par p est 1.  Vérifions le avec p=3 : 23-1 =22 =4 et la division de 4 par 3 donne 1 reste 1.

Ce résultat est intéressant, mais comme p est déjà considéré comme un très grand nombre, 2p-1 est un nombre vraiment astronomique! Si p a des centaines de chiffres, 2p-1 aura plus de chiffres que d’atomes dans l’univers! Il faut donc trouver une méthode efficace pour faire ce calcul. On veut calculer le reste de la division de 1*ab par p.

  • Si b est pair, alors 1*ab=1*(a2)b/2. On calcule a2 et on prend le reste de sa division par p.
  • Si b est impair, alors 1*ab=1*a2((b-1)/2)+1=(1*a)*(a2)(b-1)/2. On calcule a2 et 1*a et on prend les restes de leurs divisions par p.

Ainsi, dans les deux cas, on obtient un exposant plus petit et les nombres en question restent toujours du même ordre de grandeur. On continuera tant que l’exposant n’est pas 1, on pourra alors multiplier le facteur (qui ne vaudra pas nécessairement toujours un) et la base finale de l’exposant, et prendre le reste de la division par p. Pour des exemples, voir le programme ici.

Il y a malheureusement un gros désavantage à ce test. Si p est un nombre premier, alors le reste de la division de 2p-1 par p est 1, mais ce n’est pas parce que le reste de la division de 2p-1 par p est 1 que  p est premier. Il ne faut pas confondre un énoncé et sa réciproque; ce serait le sophisme de l’affirmation du conséquent, une faute de logique. En fait, il existe quelques nombres assez rares qui vérifient cette condition, mais qui ne sont pas premiers, le plus petit étant 341=11*31. Pour réduire le risque d’erreur, on peut tester avec une autre base dans l’exposant au lieu de deux. Il faut simplement que la base ne soit pas un multiple du nombre à tester (allez voir ce qui se passe dans ce cas dans le programme!). Mais, certains nombres appelés nombres de Carmichael, comme 561=3*11*17, ne fonctionnent pas avec toutes les bases qui ne sont pas copremières avec eux. La prochaine année qui sera un nombre de Carmichael est 2465; la dernière était 1729. Ainsi, ce test ne permet pas de déterminer à coup sûr si un nombre est premier, mais si un nombre échoue pour une certaine valeur, il est certainement un nombre composé. Donc, ce test peut parfaitement vérifier si un nombre n’est pas premier.

Texte et programme : Kevin Thouin, étudiant au baccalauréat en mathématiques