Voir la source de Divisions successives

{{Ébauche|informatique théorique|mathématiques}}
{{À sourcer|date=septembre 2020}}
{{Infobox}}
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 [[Nombre premier|premier]] ([[test de primalité]]) ou s'il est [[Nombre composé|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 [[Théorie de la complexité (informatique théorique)|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''}} <ref>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''}}.</ref>.

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 [[Nombre composé|composé]]. On peut poursuivre la méthode par [[itération]]s 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'' <ref>Un nombre entier est  divisible par 2 si et seulement s'il se termine par 0, 2, 4, 6, ou 8.</ref>, ou pour la divisibilité par 3 ou 9 par la vérification de la somme de ses chiffres<ref>Un nombre ''n'' est divisible par 3 (resp 9) si et seulement si la somme de ses chiffres est divisible par 3 (resp 9).</ref>. Pour plus de précisions, voir les [[critère de divisibilité|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 {{math|π({{sqrt|''n''}})}} divisions à faire, où {{math|π(''x'')}} est la fonction donnant la [[fonction de compte des nombres premiers|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 à :
:<math> \frac {\sqrt n} {\ln n} </math>  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]])<ref>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é {{frac|2}} que 2 soit un facteur de ''n'', une probabilité {{frac|3}} que 3 soit un facteur, et ainsi de suite. Il peut être montré (voir l'article sur la [[Densité asymptotique|densité]])  que 88 % de tous les entiers positifs ont un facteur inférieur à 100, et que 91 % ont un facteur inférieur à {{formatnum:1000}}.</ref>.

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|date=février 2021}}
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|date=février 2021}}

L'algorithme des divisions successives est pour ces raisons qualifié en informatique d'algorithme inefficace [[Complexité dans le pire des cas|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 [[Décomposition en produit de facteurs premiers#Algorithmes de factorisation|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 [[Éléments (Euclide)|Eléments]], couvrent de très nombreux aspects des mathématiques. Le [[Livre VII des Éléments d'Euclide|livre 7 des Eléments]] est consacré à l'arithmétique. Il contient plusieurs définitions, ''propositions'' et [[Théorème|théorèmes]] qui fondent la méthode des divisions successives. La proposition 31 énonce ainsi que {{citation|tout nombre composé est mesuré par quelques nombres premiers}} et  la proposition 32 que {{citation|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|É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ématiques)|crible]] mathématique connue à ce jour.

== Notes et références ==
{{Traduction/Référence|en|Trial division|8622386|type=note}}
{{Références}}

{{Portail|informatique théorique|arithmétique}}

[[Catégorie:Algorithme de factorisation des entiers]]
[[Catégorie:Divisibilité et factorisation]]