Factorización con fracciones continuas

De Wikipedia, la enciclopedia libre

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,[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

.

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 , en las notaciones O y L respectivamente.[3]

Referencias[editar]

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