Factorisation par fraction continue

En mathématiques, et plus particulièrement en théorie des nombres, la méthode de factorisation par fraction continue (en anglais « continued fraction factorization method », abrégé en CFRAC) est une méthode de la théorie des nombres qui détermine deux diviseurs d'un entier naturel, pourvu qu'il ne soit pas un nombre premier. Par application répétée de la méthode on obtient la décomposition en produit de facteurs premiers de ce nombre. La méthode est générale en ce sens qu'elle s'applique à tous les entiers, indépendamment d'une forme ou de propriétés particulières.

La méthode de factorisation par fraction continue a été publiée en 1931 par Derrick Henry Lehmer et Ralph Ernest Powers (en)[1], un mathématicien amateur connu aussi pour ses résultats de calculs en théorie des nombres. Elle n'a été utilisée que tardivement parce que les machines à calculer n'étaient pas assez rapides. En 1975, Michael A. Morrison et John Brillhart ont programmé la méthode sur un ordinateur plus important et ont pu obtenir la factorisation du septième nombre de Fermat[2]. La méthode de factorisation par fraction continue est resté la méthode standard de factorisation de « grands » entiers qui, pendant les années 1980, comportaient jusqu'à cinquante positions décimales. En 1990, un nouvel algorithme, la méthode du crible quadratique a remplacé la méthode par fraction continue.

La complexité en temps de la factorisation par fraction continue d'un entier est en [3].

Principe modifier

L'algorithme cherche une congruence de la forme

 .

Pour ce faire, il multiplie des congruences approprées de la forme  . À l'aide de ces congruence, on obtient une factorisation de N par la méthode de factorisation de Dixon. x2 ≡ y2 (mod N).

La méthode utilise, pour trouver ces congruences, le développement en fraction continue de  . Ce développement fournit les meilleures approximations de   sous la forme de fractions  . Chaque approximation fournit une congruence de la forme cherchée  , avec   et  . Comme la fraction est une meilleure approximation de  , l'entier   est petit et est, avec une probabilité élevée, friable, et il suffit de peu de telles congruences.

Éléments historiques modifier

La première étape vers la méthode des fractions continues est la méthode de factorisation de Fermat décrite par Pierre de Fermat en 1643. Elle consiste en la recherche de deux carrés   et   tels que  . Comme  , les entiers   et   sont alors des diviseurs de  .

En 1798, Adrien-Marie Legendre publie son livre Essai sur la théorie des nombres. On y trouve un développement de la méthode de Fermat, où la différence   est un multiple arbitraire de   ; les nombres   et   doivent satisfaire les conditions  ,   et  . Sous ces hypothèses,   divise   et les pgcds   et   sont des diviseurs de  .

Notes et références modifier

Bibliographie modifier

  • Derrick H. Lehmer et Ralph E. Powers, « On Factoring Large Numbers », Bulletin of the American Mathematical Society, vol. 37, no 10,‎ , p. 770–776 (DOI 10.1090/S0002-9904-1931-05271-X).
  • Michael A. Morrison et John Brillhart, « A Method of Factoring and the Factorization of F7 », American Mathematical Society, vol. 29, no 129,‎ , p. 183–205 (DOI 10.2307/2005475, JSTOR 2005475, lire en ligne)