Factorización con fracciones continuas

En teoría de números, la factorización con fracciones continuas, conocido como método de factorización con fracciones continuas (CFRAC del inglés Continued Fraction Factorization Method ) es un algoritmo de factorización de enteros. Es un algoritmo de propósito general, lo que significa que se puede utilizar para factorizar cualquier entero n, no dependiente de una forma espacial o de determinadas propiedades. Fue descrito por D. H. Lehmer y R. E. Powers en 1931, y desarrollado como un algoritmo de computadora por Michael A. Morrison y John Brillhart en 1975.

El método de fracciones continuas está basado sobre el método de factorización de Dixon. Este usa convergentes en las expansiones de fracciones continuas regulares de

$\sqrt{kn},k\in {\mathbb{Z}}^{\mathbb{+}}$.

Puesto que es un irracional cuadrático, la fracción continua debe de ser periódica (a no ser que n sea un cuadrado, en cuyo caso la factorización es obvia).

Este tiene un tiempo de complejidad $O\left(e^{\sqrt{2\log n\log \log n}}\right)=L_n[1/2,\sqrt{2}]$, en las notaciones O y L respectivamente.