Divisions successives

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En arithmétique et en algorithmique, la méthode par divisions successives est l’algorithme le plus simple de test de primalité ou de factorisation d'entiers naturels. Sa mauvaise complexité le rend néanmoins inadéquat pour traiter des grands nombres.

Soit donné un entier n. La méthode par divisions successives consiste à essayer de diviser n par chaque nombre premier inférieur ou égal à n. Dès qu’un test de divisibilité réussit, un facteur premier de n a été trouvé, et l’on peut déjà conclure que n est composé. Si voulu, on peut poursuivre la méthode pour obtenir la factorisation complète de n.

L’entier n admet au plus un facteur premier supérieur à n. Par conséquent, si n est composé, alors tous ses facteurs premiers sauf peut‐être un sont inférieurs à n, et l’algorithme ci‐dessus est donc assuré de les trouver. Si l’algorithme ne trouve aucun facteur, cela prouve au contraire que n est premier.

La méthode peut être légèrement optimisée. 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é à 2 par vérification du dernier chiffre, et à 3 par la vérification de la somme des chiffres. Pour plus de précisions, voir les critères de divisibilité.

L’algorithme des divisions successives est inefficace dans le pire des cas. Il effectue π(n) tests de divisibilité, où π(x) est la quantité de nombres premiers inférieurs à x. Quand n tend vers l’infini, le nombre de tests de divisibilité de l’algorithme est donc proportionnel à :

qui est une fonction exponentielle de la taille de l’entier n. Ceci signifie que pour factoriser un entier comportant de grands facteurs premiers d'une taille similaire (comme ceux utilisés pour les clés de cryptographie asymétrique), la méthode par divisions successives requiert un nombre d'opérations rédhibitoire. L’emploi d’algorithmes plus efficaces est nécessaire.

En outre, le coût ci‐dessus ne tient pas compte du calcul de la liste des nombres premiers à tester. La variante encore plus simple qui teste la divisibilité de n par chaque nombre impair inférieur à n, premier ou non, effectue n/2 tests de divisibilité.

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é 12 que 2 soit un facteur de n, une probabilité 13 que 3 soit un facteur, et ainsi de suite. Il peut être montré que 88 % de tous les entiers positifs ont un facteur inférieur à 100, et que 91 % ont un facteur inférieur à 1 000.[réf. nécessaire]

(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).