NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 14/02/2015

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Nombres PREMIERS

 

Débutants

Nombres

Premiers

Factorisation

 

Glossaire

Nombres

Premiers

 

 

INDEX

 

Nombres premiers

 

Divisibilité

Factorisation

 Fermat

 

Sommaire de cette page

>>> Approche

>>> Factorisation de Fermat

>>> Accélération des calculs

>>> Commentaires

 

 

 

 

 

Factorisation des nombres

Méthode de Fermat

 

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

attention.png  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² – 

 

*      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: x1

 

 

*      Deuxième essais: x2 = x1 + 1

 

 

 

 

 

*      Troisième essais: x3 = x2 + 1

 

 

 

 

 

 

*      Quatrième essais: x4 = x3 + 2

 

y1 = x1² - N

 

y2 = x2² - N

    = (x1 + 1)² - N

    = x1² + 2x1 + 1 – N

    = y1 + 2x1 + 1

 

y3 = x3² - N

    = (x2 + 1)² - N

    = x2² + 2x2 + 1 – N

    = y2 + 2(x1 +1) + 1

    = y2 + 2x1 + 1 + 2

 

 

y4 = y3 + 2x1 + 3 + 2

 

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

*  en notant: 2x1 + 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.

 

X

a = 2 x 37+1+2k

 

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

 

 

 

 

Commentaires

 

*      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 dispose 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

*    FactorisationIndex

Voir

*    Nombres premiersIndex

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