Divisions successives

En arithmétique, la méthode par divisions successives est la méthode la plus simple et la plus ancienne pour déterminer si un nombre entier naturel est premier (test de primalité) ou s'il est composé, pour en trouver la décomposition en produit de facteurs premiers.

Cette méthode est utilisable en algorithmique. Très pratique pour tester de petits nombres, elle est peu efficace pour de grands nombres du fait de sa mauvaise complexité.

Principe de la méthode

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 à $\sqrt n$ , car tout entier n admet au plus un facteur premier supérieur à $\sqrt 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é.

Efficacité de la méthode

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 $π(\sqrt 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 à :

{\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. ^[pas clair] La variante plus simple qui teste la divisibilité de n par chaque nombre impair inférieur à $\sqrt n$ , premier ou non, demande encore d'effectuer $\sqrt n$ /2 tests de divisibilité.^[pas clair] 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.

Origines historiques

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.

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Trial division » (voir la liste des auteurs).

Si n est premier, la propriété est évidente, puisque n n'est divisible que par lui-même. Si n est composé, supposons qu’il ait 2 diviseurs premiers différents supérieurs ou égaux à $\sqrt n$ : p et q. Comme ils sont différents, l’un d'entre eux au moins est strictement supérieur à $\sqrt n$ . Donc p*q est strictement plus grand que n, ce qui est impossible, puisque n est un multiple de p et de q, donc de p*q, donc au moins égal à p*q. Ce raisonnement par l'absurde montre que n ne peut avoir qu'un seul diviseur premier supérieur ou égal à $\sqrt n$ .
Un nombre entier est divisible par 2 si et seulement s'il se termine par 0, 2, 4, 6, ou 8.
Un nombre n est divisible par 3 (resp 9) si et seulement si la somme de ses chiffres est divisible par 3 (resp 9).
Néanmoins, si n comporte au moins un petit facteur, les divisions successives peuvent être une manière rapide de trouver ce petit facteur. Pour un entier n aléatoire, il y a une probabilité ¹⁄₂ que 2 soit un facteur de n, une probabilité ¹⁄₃ que 3 soit un facteur, et ainsi de suite. Il peut être montré (voir l'article sur la densité) que 88 % de tous les entiers positifs ont un facteur inférieur à 100, et que 91 % ont un facteur inférieur à 1 000.

Portail de l'informatique théorique
Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Si n est premier, la propriété est évidente, puisque n n'est divisible que par lui-même. Si n est composé, supposons qu’il ait 2 diviseurs premiers différents supérieurs ou égaux à $\sqrt n$ : p et q. Comme ils sont différents, l’un d'entre eux au moins est strictement supérieur à $\sqrt n$ . Donc p*q est strictement plus grand que n, ce qui est impossible, puisque n est un multiple de p et de q, donc de p*q, donc au moins égal à p*q. Ce raisonnement par l'absurde montre que n ne peut avoir qu'un seul diviseur premier supérieur ou égal à $\sqrt n$ .

[2] Un nombre entier est divisible par 2 si et seulement s'il se termine par 0, 2, 4, 6, ou 8.

[3] Un nombre n est divisible par 3 (resp 9) si et seulement si la somme de ses chiffres est divisible par 3 (resp 9).

[4] Néanmoins, si n comporte au moins un petit facteur, les divisions successives peuvent être une manière rapide de trouver ce petit facteur. Pour un entier n aléatoire, il y a une probabilité ¹⁄₂ que 2 soit un facteur de n, une probabilité ¹⁄₃ que 3 soit un facteur, et ainsi de suite. Il peut être montré (voir l'article sur la densité) que 88 % de tous les entiers positifs ont un facteur inférieur à 100, et que 91 % ont un facteur inférieur à 1 000.