Les nombres premiers sont les briques élémentaires des entiers : tout entier supérieur à 1 est soit premier, soit le produit unique de nombres premiers. Cette calculatrice teste la primalité, décompose les nombres en facteurs et liste les nombres premiers d’un intervalle, même pour des nombres bien trop grands pour un tableur, grâce au test de Miller-Rabin également utilisé en cryptographie moderne.
Qu’est-ce qui caractérise un nombre premier ?
Un nombre premier possède exactement deux diviseurs positifs : 1 et lui-même. Cette définition exclut 1 (qui n’a qu’un seul diviseur) et 0 (qui est divisible par tous les nombres) ; le plus petit nombre premier est donc 2, et c’est le seul nombre premier pair, puisque tout autre entier pair est divisible par 2.
Pour vérifier un nombre à la main, il suffit de tester les diviseurs jusqu’à sa racine carrée. Si aucun entier de 2 à √n ne divise n, alors n est premier. C’est pourquoi il suffit de quatre divisions par essais (2, 3, 5 et 7) pour vérifier 97, plutôt que d’en tester 95.
Factorisation et crible
Le théorème fondamental de l’arithmétique garantit que tout entier supérieur à 1 se décompose d’une seule manière en nombres premiers. La décomposition en facteurs premiers est à la base de la simplification des fractions et du calcul des plus petits communs multiples. Cet outil utilise la division par essais pour extraire successivement le plus petit facteur premier jusqu’à ce qu’il ne reste que 1.
Pour trouver tous les nombres premiers d’un intervalle, la méthode classique la plus rapide est le crible d’Ératosthène : on liste les nombres, puis on barre les multiples de 2, puis de 3, de 5, et ainsi de suite. Les nombres qui restent sont premiers. Un crible segmenté applique la même méthode à la seule plage demandée, ce qui le rend rapide même sur des millions de nombres.
Grands nombres et cryptographie
La division par essais devient inutilisable lorsque les nombres sont grands : tester un nombre de 60 chiffres prendrait plus longtemps que l’âge de l’Univers. La calculatrice passe alors au test de Miller-Rabin, qui utilise l’exponentiation modulaire pour déterminer la primalité en une fraction de seconde. Avec un ensemble fixe de bases témoins, ce test est rigoureusement exact pour tout nombre inférieur à 3.3 × 10²⁴.
C’est important, car les grands nombres premiers sont au fondement de la cryptographie à clé publique. Le chiffrement RSA multiplie deux énormes nombres premiers pour former une clé publique ; sa sécurité repose sur la difficulté extrême de retrouver ces deux nombres à partir de leur produit, alors qu’il est facile de tester la primalité d’un candidat. Cette différence entre un test de primalité rapide et une factorisation lente protège les communications chiffrées.