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 en 1931,​ y desarrollado como un algoritmo de computadora por Michael A. Morrison y en 1975.​ El método de fracciones continuas está basado sobre el método de factorización de Dixon. Este usa en las expansiones de fracciones continuas regulares de . Puesto que es un , la fracción continua debe de ser (a no ser que n sea un cuadrado, en cuyo caso la factorización es obvia). Este tiene un tiempo de complejidad , en las notaciones O y repectivamente.​