NOMBRES – Curiosités, Théorie et Usages Accueil DicoNombre Rubriques Nouveautés Édition du: 27/10/2021 Orientation générale  DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	Nombres PREMIERS
Débutants Nombres Premiers	Factorisation				Glossaire Nombres Premiers
INDEX Factorisation Nombres premiers	Divisibilité	Factorisation	Fermat	Shor
		Sommaire de cette page >>> Trouver les facteurs d'un nombre >>> Historique >>> Approche >>> Première méthode, la plus commune >>> Deuxième méthode – Le modulo >>> Fermat et son petit théorème >>> Algorithme AKS >>> Wilson et son théorème >>> Nombres de Mersenne >>> Factorisation de Fermat >>> BILAN

Primalité & Factorisation

des nombres

 Deux problèmes successifs:

Déterminer si un nombre est premier: primalité;

Trouver ses facteurs premiers: factorisation.

Trouver les facteurs d'un nombre est utile en général, mais a regagné de l'intérêt ces dernières décennies du fait que les codes de sécurité des échanges informatiques sont basés sur la grande difficulté (impossibilité) de factoriser de très grands nombres.

Trouver les facteurs d'un nombre

Sur ces pages

Pour les facteurs des nombres de 1 à 1000 >>>

Pour les nombres premiers de 1 à 10 000 >>>

Pour une majorité des nombres: factorisation et propriétés >>>

Sur Internet

Tapez isprime (votre nombre) dans un moteur de recherche et vous aurez le choix.

Exemple: https://www.integers.co/questions-answers/what-is-the-prime-factorization-of-the-number-123456789.html

Calculateur en ligne: https://www.integers.co/tools/calculator.html

Entrez votre nombre et choisissez la fonction find the prime factorisation dans le menu déroulant.

Gauss (1801)

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic.

C.F. Gauss – 1801 - Disquisitiones Arithmeticae

Historique

Avant les machines Au XVII^e siècle: table des facteurs des nombres jusqu'à 24000. 1668: tous jusqu'à 100 000. Au XVII^e siècle: tous jusqu'à 10 000 000 par Johann Dase (1824-1861) Au XIX^e siècle: 100 000 000 par J.P. Kulik (Prague) avec quelques erreurs. Au-delà, ces tables ne tiennent plus sur du papier. Avec les machines Un des premiers grands nombres factorisés par machine (Lehmer): 2^93 + 1 = 9 903 520 314 283 042 199 192 993 793 = 0,99… 10^28 = 6 442 450 947 x 1 537 228 672 093 301 419 = 6 442 450 947 x 529 510 939 x 2 903 110 321 1971: factorisation d'un nombre "difficile" de 40 chiffres. 1982: Supercalculateur (Cray 1) craque les 50 chiffres. 1988: Facteur k trouvé en 1988 par coopération de centaines d'ordinateurs. k = 11^104 + 1 / 11^8 + 1. La limite des 100 chiffres est atteinte. Pour se trouver en zone sûre, le codage en cryptographie adopte des nombres à 200 chiffres. 2010: Factorisation du RSA 768 >>>

D'après: Dites un chiffre de Malcom Lines - Flammarion

Approche
Factoriser un nombre consiste à: Identifier que le nombre est composé, et non pas premier, et à Trouver des facteurs premiers dont le produit redonne ce nombre. Le théorème fondamental de l'arithmétique nous indique que cette factorisation est unique.	111 n'est pas premier, la somme de ses chiffres est égale à 3 ce qui indique qu'il est divisible par 3 et donc pas premier; Avec une petite division, on trouve l'autre facteur: 111 = 3 x 37.

Première méthode – la plus commune

Trouver si le nombre est divisible par un autre:

par utilisation de critères de divisibilités, ou

par essais par divisions avec des nombres premiers de plus en plus grands. La recherche s'arrête lorsqu'on atteint un diviseur supérieur à la racine carrée du nombre

On notera immédiatement qu'il est illusoire d'appliquer cette méthode aux très grands nombres.

La recherche de divisibilité est assez facile pour les nombres 2, 3, 5 et 11 (et leurs multiples).

456 = 2 x 228

453 = 3 x 151

455 = 5 x 91

459 = 9 x 51

450 = 10 x 45

451 = 11 x 41

Ayant épuisé ces possibilités, il faut recourir à la division classique:

469	7
04 49 00	67

Deuxième méthode – Modulo
Le principe est simple: une buche est bien coupée en stère s'il n'y a pas de chute. Les mathématiciens ont créé un nouveau monde, un nouvel espace de travail. Un espace où seul le reste de la division compte. Les calculs dans ce monde seront plus propices à débusquer les nombres composés. Nous utilisons tous les jours cette technique en regardant nos montres. Toutes les 12 heures nous revenons à 0. Les mathématiciens parlent de congruence ou de modulo. Cette arithmétique en modulo marche aussi avec les opérations.	Un nombre est divisible par n si le reste de sa division par n est nul. Un nombre divisé par 7 donne les restes 0, 1, 2,3 ,4 5 et 6; seul le reste 0 montre que le nombre est divisible par 7. Minuit et midi sont des horaires multiples de 12. Le calcul de l'horloge fait que 14h devient 2h. On a retiré 12heures. 14 2 mod 12 2 est congru à 14 modulo 12 Ce qui veut dire que, dans le monde du 12, 2 et 14 sont équivalents. 9 + 5 = 14 2 mod 12 11 + 12 = 23 11 mod 12 12 + 12 = 24 0 mod 12 13 + 12 = 25 1 mod 12 9 x 4 = 36 0 mod 12 9 x 5 = 45 9 mod 12
Si, d'une manière ou d'une autre, je connais la congruence d'un nombre N modulo M, je sais dire s'il est divisible par M. Bien noter que je ne sais pas conclure si le nombre est premier. Pour cela , il faudrait essayer toutes les valeurs de congruence.	109 824 87 mod 89 109 825 88 mod 89 109 826 0 mod 89 Ce dernier nombre est composé: 109 826 = 89 x 1234.

FERMAT et son petit théorème
Fermat s'intéresse aux modulos selon des nombres premiers p. Il remarque qu'un nombre a et sa puissance p sont égaux (congruents). Même déguisé en puissance p, le scanner modulo p, déshabillera l'individu pour le mettre à nu: a^p devient a. En langage mathématique: a puissance p est égal à a modulo p. Exemples (Le reste de 32 divisé par 5 est 2)	Tout nombre a, déguisé en puissance p, se faisant happer par la machine à modulo p, sera haché menu pour recracher tout ce qu'il a.

Voir suite et exemples en Modulo / Divisibilité par 11

Algorithme AKS

En 2002, Manindra Agrawal (Kapur, Inde), Neeraj Kayal et Nitin Saxena (AKS), annoncent avoir trouvé un test de primalité rapide dérivant du petit théorème de Fermat. Agrawal résume sa découverte par "Les premiers sont en P". Ce qui veut dire que la temps de calcul de la primalité est, en gros, proportionnel à sa quantité de chiffres.

C'est, rapide mais encore assez pour déjouer les systèmes de cryptage.

Théorème de Wilson
Ce théorème se propose de traquer les nombres premiers aux abords des nombres factoriels.	(n – 1)! + 1 est divisible par n, seulement si n est premier. Pour n = 5: 4! + 1 = 25, divisible par 5

Voir suite et exemples en Théorème de Wilson

Nombres de Mersenne
Cette recherche traque les nombres premiers aux abords des puissances de 2. La méthode utilisée permet de reconnaître de très grands nombres premiers, en fait les plus grands connus aujourd'hui. À noter, qu'il s'agit du premier pas (premier ou composé) et non pas de la factorisation.	2^4 – 1 = 15 =3 x 5 2^5 – 1 = 31 premier 2^6 – 1 = 63 = 3 x 3 x 7 2^7 – 1 = 127 premier etc.

Voir Primalité des nombres de Mersenne

Factorisation de Fermat
Voir page spéciale >>> Ce test a été amélioré par Maurice Kraitchik en utilisant les modulos des carrés.

Autres méthodes
De nombreux algorithmes ont été développés. Cela dépasse le cadre de ce site. La factorisation est d'autant plus difficile que les facteurs sont de tailles voisines.

Voir factorisation de Lenstra

BILAN – Méthodes les plus accessibles
Selon ce que l'on cherche	Premier ou composé?	Facteurs
Tout nombre	· Critères de divisibilité · Congruences (modulos) Théorème de Wilson Petit théorème de Fermat	· Crible d'Ératosthène · Méthode de Fermat
Nombres spécifiques	· Mersenne (2^n – 1) Test de Lucas-Lehmer	· Nombres divisibles d'après un critère de divisibilité.

Factorisation Index	Cribles – Types de cribles Factorisation des factorielles Factorisation des nombres complexes Factorisation des puissances de 21 Nombres RSA Méthode algorithmique Méthode avec deux carrés Méthode de Fermat Méthode des frères Carissan (crible des résidus quadratiques) Méthode René Nève – Sommes de pairs et des impairs Méthodes générales Méthode ECM de recherche de grands facteurs
Voir	Nombres premiers – Index
Aussi	Liste de nombres premiers Nombres composés Représentation des nombres Facteurs premiers autour de 1000 Premiers en tableaux, en spirales …
Site	Algorithmes de factorisation à l'envi – Cyril Banderier – 1999/97 Factorisation d'entiers – Pascal Molin Arithmétique algorithmique – Roblot – Diaporama Prime Factors Calculator
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Premier/Facto.htm