Factorización de fracciones continua

En teoría de números , el método de factorización de fracciones continuas ( CFRAC ) es un algoritmo de factorización de enteros . Es un algoritmo de propósito general, lo que significa que es adecuado para factorizar cualquier entero n , sin depender de formas o propiedades especiales. Fue descrito por D. H. Lehmer y R. E. Powers en 1931 ^{[ 1 ]} y desarrollado como algoritmo informático por Michael A. Morrison y John Brillhart en 1975 ^{[ 2 ].}

El método de fracciones continuas se basa en el método de factorización de Dixon . Utiliza convergentes en la expansión regular de fracciones continuas de

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

Dado que se trata de un número irracional cuadrático , la fracción continua debe ser periódica (a menos que n sea cuadrado, en cuyo caso la factorización es obvia).

Tiene una complejidad temporal de${\displaystyle O\left(e^{\sqrt {2\log n\log \log n}}\right)=L_{n}\left[1/2,{\sqrt {2}}\right]}$, en las notaciones O y L. ^{[ 3 ]}

• Samuel S. Wagstaff, Jr. (2013). El placer de factorizar . Providence, RI: American Mathematical Society. pp. 143–171 . ISBN  978-1-4704-1048-3.