s
19 708 Pages

la Procédé de factorisation de Fermat est un algorithme conçu par Pierre de Fermat pour affacturage des nombres entiers dans sa principaux facteurs. Il est basé sur la représentation d'un nombre comme la différence entre deux carré, et il est plus efficace quand il y a deux facteurs du nombre de plus près les uns des autres.

algorithme

  1. les deux n un nombre entier impair.
  2. (où Il indique la fonction entier supérieur).
  3. répétition
    1. si est pas un carré parfait alors
  4. jusqu'à ce que Ce n'est pas un carré parfait.

explication

supposer n est un entier impair, et qu'il existe deux entiers à et b de telle sorte que n = ab (avec à>b). puis

puis n est la différence de deux carrés. être n un nombre entier impair, même à et b il doit être à son tour: Donc, les chiffres d = a + b et c = a-b Ils sont égaux, et leur somme est un nombre entier. l'expression On peut donc être considérée comme , et, , est une factorisation est obtenue non triviale n.

L'algorithme est donc de calculer le nombre jusqu'à ce que vous trouver un carré parfait; puis

Le calcul des carrés successifs est également facilitée par le fait que les différences entre les carrés consécutifs ont formé un progression arithmétique Raison n ° 2: . La reconnaissance des places peut se faire soit par les méthodes de arithmétique modulaire (Ce qui élimine de nombreuses possibilités pour les places: par exemple la dernière décimale peut non seulement être 2, 3, 7 ou 8) ou par des tables carrés spéciales.

généralisations

Au XXe siècle, différents algorithmes d'affacturage ont été proposés qui ont été calqué sur celui de Fermat. Maurice Kraitchik suggéré dans les années vingt que, au lieu de considérer l'ensemble x et y de telle sorte que , vous pourriez plutôt essayer de sorte que ceux-ci n diviser la différence entre les carrés, qui recherchent des solutions de congruence

ou de manière équivalente

Dans ce contexte, les solutions « intéressantes » de congruence sont ceux dans lesquels x Il est pas raisonnable, ni y ou -y forme n et où les deux x et y ils sont me couvrir avec n. si n est impair et divisible par au moins deux premières, il a été montré qu 'au moins la moitié des solutions sont intéressantes. Dans ce cas |x-y| Il est composé strictement entre 1 et n, et il est donc un facteur non négligeable n.

Cette idée a été fondée à la fois l'algorithme des fractions continues qui tamis quadratique.

bibliographie

  • Keith Devlin, D'où vient le calcul. Bollati Basic Books, Torino, 1994. ISBN 88-339-1182-9
  • Harold Davenport, plus arithmétique. Zanichelli, Bologne, 1994. ISBN 88-08-09154-6

liens externes