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 Modèle:Citation étrangère, 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^[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 $N$ est en Modèle:Retrait

Principe

L'algorithme cherche une congruence de la forme

x^{2} \equiv y^{2} mod N

.

Pour ce faire, il multiplie des congruences approprées de la forme $x^{2} \equiv y mod 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 $\sqrt{N}$ . Ce développement fournit les meilleures approximations de $\sqrt{N}$ sous la forme de fractions $p / q$ . Chaque approximation fournit une congruence de la forme cherchée $x^{2} \equiv y mod N$ , avec $x = p$ et $y = x^{2} - q$ . Comme la fraction est une meilleure approximation de $\sqrt{N}$ , l'entier $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 $x^{2}$ et $y^{2}$ tels que $x^{2} - y^{2} = N$ . Comme $N = x^{2} - y^{2} = (x + y) (x - y)$ , les entiers $x + y$ et $x - y$ sont alors des diviseurs de $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 $x^{2} - y^{2}$ est un multiple arbitraire de $N$ ; les nombres $x$ et $y$ doivent satisfaire les conditions $0 < x, y < N$ , $x \neq y$ et $x + y \neq N$ . Sous ces hypothèses, $N$ divise $x^{2} - y^{2} = (x + y) (x - y)$ et les pgcds $pgcd (N, x + y)$ et $pgcd (N, x - y)$ sont des diviseurs de $N$ .