Divisions successives

Soit un entier naturel n. La méthode par divisions successives consiste à essayer de diviser n par chaque nombre premier qui lui est inférieur, en commençant par 2, puis 3, puis 5, et ainsi de suite.

En pratique on n'aura à essayer cette division que jusqu'au premier nombre premier supérieur ou égal à √n, car tout entier n admet au plus un facteur premier supérieur à √n [1].

Dès qu’un test de divisibilité réussit, un facteur premier de n a été trouvé : on peut déjà conclure que n est composé. On peut poursuivre la méthode par itérations successives pour obtenir la factorisation complète de n.

Si n est composé, l’algorithme ci‐dessus est donc assuré de le prouver et de trouver les facteurs le composant. Si l’algorithme ne trouve aucun facteur, cela prouve au contraire que n est premier.

La méthode peut être optimisée pour limiter le nombre de divisions à tenter. Par exemple, si le dernier chiffre de n n'est ni 0 ni 5, il est inutile de tester le facteur 5. Le même argument peut être appliqué à la division par 2 par vérification du dernier chiffre de n [2], ou pour la divisibilité par 3 ou 9 par la vérification de la somme de ses chiffres[3]. Pour plus de précisions, voir les critères de divisibilité.

Pour prouver qu'un nombre n est premier, la méthode va devoir tester la divisibilité de n par tous les nombres premiers inférieurs ou égaux à racine carrée de n. Il y a donc π(√n) divisions à faire, où π(x) est la fonction donnant la quantité de nombres premiers inférieurs à x.

D'après le théorème des nombres premiers , quand n tend vers l’infini, le nombre de tests de divisibilité de l’algorithme est donc proportionnel à :

${\displaystyle {\frac {\sqrt {n}}{\ln n}}}$ qui est une fonction exponentielle de la taille de l’entier n.

Ceci signifie que pour prouver qu'un entier de grande taille est premier, la méthode par divisions successives requiert un nombre d'opérations rédhibitoire. Il en est de même lorsque la méthode est utilisée pour prouver qu'un entier est composé alors qu'il ne contient que de grands facteurs premiers (comme ceux utilisés pour les clés de cryptographie asymétrique)[4]. En outre, le nombre d'opérations mentionné ci‐dessus ne tient pas compte du calcul de la liste des nombres premiers à tester. La variante plus simple qui teste la divisibilité de n par chaque nombre impair inférieur à √n, premier ou non, demande encore d'effectuer √n/2 tests de divisibilité. L’algorithme des divisions successives est pour ces raisons qualifié en informatique d'algorithme inefficace dans le pire des cas.

Pour trouver (ou tester) de très grands nombres premiers, ou pour factoriser des nombres composés avec de très grands facteurs premiers, les spécialistes lui préfèreront des algorithmes plus efficaces.

Les plus anciens écrits concernant les nombres premiers sont attribués au mathématicien grec Euclide, qui aurait vécu vers -300 avant J-C. Les travaux d'Euclide, notamment ceux regroupés dans les 13 livres constituant le traité des Eléments, couvrent de très nombreux aspects des mathématiques. Le livre 7 des Eléments est consacré à l'arithmétique. Il contient plusieurs définitions, "propositions" et théorèmes qui fondent la méthode des divisions successives. La proposition 31 énonce ainsi que "tout nombre composé est mesuré par quelques nombres premiers" et la proposition 32 que "tout nombre est premier ou mesuré par quelques premiers".

Les travaux d'Euclide ont été la base des très nombreux développements mathématiques ultérieurs concernant les nombres premiers.

Ainsi, quelques décennies après Euclide, Ératosthène de Cyrène, mathématicien grec mort vers -198 avant J-C, invente la première méthode permettant de rechercher les nombres premiers inférieurs à tout entier n : c'est le crible d'Ératosthène. Cette méthode, qui s'appuie sur les propositions d'Euclide, permet d'éliminer par itérations tous les nombres inférieurs à n qui sont premiers (ou composés mais n'ont pas de diviseurs communs avec n). Il s'agit de la plus ancienne méthode de crible mathématique connue à ce jour.