Factorización con fracciones continuas

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 es apropiado para factorizar cualquier entero n, no dependiente de una forma espacial o de propiedades. Fue descrito por D. H. Lehmer y R. E. Powers en 1931,[1] y desarrollado como un algoritmo de computadora por Michael A. Morrison y John Brillhart en 1975.[2]

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},\qquad k\in\mathbb{Z^+}.

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\left[1/2,\sqrt{2}\right], en las notaciones O y L repectivamente.[3]

Referencias[editar]

  1. Lehmer, D.H.; Powers, R.E. (1931). «On Factoring Large Numbers». Bulletin of the American Mathematical Society 37 (10):  pp. 770–776. doi:10.1090/S0002-9904-1931-05271-X. 
  2. Morrison, Michael A.; Brillhart, John (January 1975). «A Method of Factoring and the Factorization of F7». Mathematics of Computation (American Mathematical Society) 29 (129):  pp. 183–205. doi:10.2307/2005475. 
  3. Pomerance, Carl (December 1996). «A Tale of Two Sieves». Notices of the AMS 43 (12). pp. 1473–1485.