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 ${\displaystyle N}$ est en ${\displaystyle O\left(e^{\sqrt {2\log N\log \log N}}\right)}$^[3].

Principe

L'algorithme cherche une congruence de la forme

${\displaystyle x^{2}\equiv y^{2}{\bmod {N}}}$.

Pour ce faire, il multiplie des congruences approprées de la forme ${\displaystyle x^{2}\equiv y{\bmod {N}}}$. À l'aide de ces congruence, on obtient une factorisation de N par la méthode de factorisation de Dixon. x² ≡ y² (mod N).

La méthode utilise, pour trouver ces congruences, le développement en fraction continue de ${\displaystyle {\sqrt {N}}}$. Ce développement fournit les meilleures approximations de ${\displaystyle {\sqrt {N}}}$ sous la forme de fractions ${\displaystyle p/q}$. Chaque approximation fournit une congruence de la forme cherchée ${\displaystyle x^{2}\equiv y{\bmod {N}}}$, avec ${\displaystyle x=p}$ et ${\displaystyle y=x^{2}-q}$. Comme la fraction est une meilleure approximation de ${\displaystyle {\sqrt {N}}}$, l'entier ${\displaystyle y}$ est petit et est, avec une probabilité élevée, friable, et il suffit de peu de telles congruences.

Éléments historiques

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 ${\displaystyle x^{2}}$ et ${\displaystyle y^{2}}$ tels que ${\displaystyle x^{2}-y^{2}=N}$. Comme ${\displaystyle N=x^{2}-y^{2}=(x+y)(x-y)}$, les entiers ${\displaystyle x+y}$ et ${\displaystyle x-y}$ sont alors des diviseurs de ${\displaystyle N}$.

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 ${\displaystyle x^{2}-y^{2}}$ est un multiple arbitraire de ${\displaystyle N}$ ; les nombres ${\displaystyle x}$ et ${\displaystyle y}$ doivent satisfaire les conditions ${\displaystyle 0<x,y<N}$, ${\displaystyle x\neq y}$ et ${\displaystyle x+y\neq N}$. Sous ces hypothèses, ${\displaystyle N}$ divise ${\displaystyle x^{2}-y^{2}=(x+y)(x-y)}$ et les pgcds ${\displaystyle \operatorname {pgcd} (N,x+y)}$ et ${\displaystyle \operatorname {pgcd} (N,x-y)}$ sont des diviseurs de ${\displaystyle N}$.

Notes et références

Bibliographie

• Carl Pomerance, « A Tale of Two Sieves », Notices of the AMS, vol. 43, n^o 12,‎ décembre 1996, p. 1473-1485 (lire en ligne).

• Derrick H. Lehmer et Ralph E. Powers, « On Factoring Large Numbers », Bulletin of the American Mathematical Society, vol. 37, n^o 10,‎ 1931, 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 F₇ », American Mathematical Society, vol. 29, n^o 129,‎ janvier 1975, p. 183–205 (DOI 10.2307/2005475, JSTOR 2005475, lire en ligne)

• Samuel S. Wagstaff, Jr., The Joy of Factoring, Providence, RI, American Mathematical Society, 2013, 293 p. (ISBN 978-1-4704-1048-3, présentation en ligne)

• Arithmétique et théorie des nombres