NOMBRES – Curiosités, Théorie et Usages Accueil DicoNombre Rubriques Nouveautés Édition du: 24/09/2022 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 Nombres premiers	Divisibilité	Factorisation	Fermat	Shor
		Sommaire de cette page >>> Approche >>> Factorisation de Fermat >>> Accélération des calculs >>> Factorisation d'un nombre à deux facteurs proches >>> Programmation >>> Commentaires et améliorations

Factorisation des nombres

Méthode de Fermat

Méthode relativement classique par essais successifs, mais avec des astuces pour accélérer la recherche.

La page sur la machine à factoriser des frères Carissan constituera sans doute une introduction plus en douceur sur ce sujet.

Approche
Si on s'intéresse aux nombres N susceptibles d'être décomposés en deux facteurs, alors l'un d'eux est plus grand que la racine de N et l'autre plus petit. Pour chercher les facteurs d'un nombre, il est possible de procéder à partir de la racine et essayer tous les nombres jusqu'à trouver les facteurs.	13 x 17 = 221 221 = 14,86 13 < 14,86 < 17 On arrondi la racine au nombre supérieur: 14,86 => 15 On essaie les nombres à partir de 15 et au-delà: 221 / 15 = 14,7 / 16 = 13, 8 / 17 = 13 Bingo!

Factorisation de Fermat
Fermat imagine un truc pratique basé sur une identité remarquable: N = (x – y) (x + y) = x² – y² Si un nombre est différence de deux carrés, il peut être factorisé. Or, tout va bien puisque: tout nombre impair est différence de deux carrés >>>	Exemple Soit N = 3 021 Sa racine est 54,96, arrondi à la valeur par excès: 55 Cette valeur devient x, et on va tester si y est un carré. y² = x² - N y² = 55² - 3 021 = 4 = 2² Y est un carré, N est factorisable: N = (55 – 2) ( 55 + 2) = 53 x 57
Si ce n'est pas un carré du premier coup, on poursuit les essais avec les nombres suivants. On reconnaît assez facilement un carré par ses deux derniers chiffres: 0, 1, 4, 9, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89 et 96. Notez aussi que les unités ne sont jamais 2, 3, 7 ou 8.	Exemple Soit N = 377 Racine: 19,4 => 20 20² - 377 = 23 pas carré 21² - 377 = 64 = 8² 377 = (21 – 8) (21 + 8) = 13 x 29

Accélération des calculs

Premier essais: x₁

Deuxième essais: x₂ = x₁ + 1

Troisième essais: x₃ = x₂ + 1

Quatrième essais: x₄ = x₃ + 1

y₁ = x₁² - N

y₂ = x₂² - N

= (x₁ + 1)² - N

= x₁² + 2x₁ + 1 – N

= y₁ + 2x₁ + 1

y₃ = x₃² - N

= (x₂ + 1)² - N

= x₂² + 2x₂ + 1 – N

= y₂ + 2(x₁ +1) + 1

= y₂ + 2x₁ + 1 + 2

y₄ = y₃ + 2x₁ + 3 + 2

La méthode d'accélération consiste à calculer y directement. Pour chaque nouvelle itération:

en notant: 2x₁ + 1 + 2k,

en lui ajoutant l'écart précédant.

Exemple

Soit N = 1313

Racine: 36,2 => 37

37² - 1313 = 56 pas carré

On va poursuivre en utilisant la méthode de Fermat.

En bleu, l'en-tête du tableau.

En jaune, la première ligne d'amorce.

La deuxième ligne: 2 x 37 + 1 + 2 x 0 = 75; faire + 2 pour les suivantes.

X	a = 2 x 37+1+2k		Y²	Carré
37		37² - 1313 =	56	N
38	75	75 + 56 =	131	N
39	77	77 + 131 =	208	N
40	79	etc.	287	N
41	81		368	N
42	83		451	N
43	85		536	N
44	87		623	N
45	89		712	N
46	91		803	N
47	93		896	N
48	95		991	N
49	97		1088	N
50	99		1187	N
51	101		1288	N
52	103		1391	N
53	105		1496	N
54	107		1603	N
55	109		1712	N
56	111		1823	N
57	113		1936	44 x 44

1 313 = (57 – 44) (57 + 44) = 13 x 101

Factorisation d'un nombre à deux facteurs proches		haut
Factoriser ce nombre dont on suspecte que les deux facteurs sont proches.	n = 809 009
Deux facteurs proches, donc autour de la racine carrée. Pas plus de cinq essais seront nécessaires.
L'idée est de chercher un produit de ce style. Avec le nombre a² proche de n, légèrement supérieur.	(a – b)(a + b) = a² – b² = 809 009 a² – 809 009 = b²
Quelques essais pour finalement trouver a = 903.
Soit la factorisation avec ces deux nombres premiers	809 009 = (903 – 80)(903 + 80) = 823 × 983

Factoriser ce nombre dont on suspecte que les deux facteurs sont proches.	n = 23 449
Carré juste supérieur (plafond de la racine carrée)	154² > 23 449
Essais	154² – 23 449 = 23 716 – 23 449 ) = 267 155² – 23 449 = 24 025 – 23 449 ) = 576 = 24²
Factorisation	n = 23 449 = (155 – 24)(155 + 24) = 179 × 131

Factoriser ce nombre dont on suspecte que les deux facteurs sont proches.	n = 119 143
Carré juste supérieur (plafond de la racine carrée)	346² > 119 143
Rappel: les deux derniers chiffres possibles pour un carré (jamais: 2, 3, 7 et 8 pour l'unité):	Essais avec calcul que si le carré se termine selon un carré.
Factorisation	n = 23 449 = (352 – 69)(352 + 69) = 283 × 421

Voir Brève 47-926

Programmation				haut
		But Énoncer les nombres produits de deux facteurs premiers proches. Commentaires Boucle d'analyse des nombres n de 10 à 100 (exemple). Calcul du plafond (ceiling) de la racine de n. Boucle de recherche des carrés parfaits. Ici, le test est limité à deux essais: la racine et son successeur. Calcul de t dont on cherche s'il est racine carrée exacte. Pour cela, test du type de nombre: est-il une entier (integer). Si oui, calcul des deux facteurs fi et f2. Impression si, de surcroit, ces deux facteurs sont premiers (isprime). Résultat Liste des douze nombres de 10 à 100, dont deux carrés. D'autres valeurs sont présentées ci-dessous.
Quelques exemples N, f1, f2, f2-f1		Ex: 1073 = 29 x 37 Écart 8

Voir Programmation – Index

Commentaires et améliorations
Avant de mettre en route la méthode de Fermat, assurez-vous que le nombre n'est pas divisible par des petits nombres avec les critères classiques de divisibilité. La méthode se prête bien à une réalisation sur tableur. (ou programmation pour ceux qui disposent des outils). La méthode a été améliorée par par Maurice Kraitchik en utilisant les modulos des carrés. Il est possible de choisir x comme produit de facteurs et de traiter la factorisation avec deux outils mathématiques: les modulos et les PGCD. Plus de détails sur les sites Internet spécialisés …	Pour 1317 = (221 – 218) (221 + 218) = 3 x 439, il faut 185 itérations, alors qu'un coup d'œil montre que ce nombre est divisible par 3. Améliorations avec considérations sur: x² y² mod n x = x1 . x2 . x3 … Si x² y² mod n, alors (x – y) (x + y) = 0 mod n, et PGCD (x + y, n) ou PGCD (x – y, n) donne un diviseur de n.

Retour	Factorisation – Index
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 …
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Premier/FactoFer.htm