En teoría de números , el método de factorización de fracción continua ( CFRAC ) es un algoritmo de factorización de números enteros . Es un algoritmo de propósito general, lo que significa que es adecuado para factorizar cualquier número entero n , sin depender de una forma o propiedades especiales. Fue descrito por DH Lehmer y RE Powers en 1931, [1] y desarrollado como un algoritmo informático por Michael A. Morrison y John Brillhart en 1975. [2]
El método de fracción continua se basa en el método de factorización de Dixon . Utiliza convergentes en la expansión fraccionaria continua regular de
- .
Dado que se trata de un 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 de tiempo de , en las notaciones O y L. [3]
Referencias
- ^ Lehmer, DH; Powers, RE (1931). "Sobre la factorización de números grandes" . Boletín de la American Mathematical Society . 37 (10): 770–776. doi : 10.1090 / S0002-9904-1931-05271-X .
- ^ Morrison, Michael A .; Brillhart, John (enero de 1975). "Un método de factorización y la factorización de F 7 " . Matemáticas de la Computación . Sociedad Matemática Estadounidense. 29 (129): 183–205. doi : 10.2307 / 2005475 . JSTOR 2005475 .
- ^ Pomerance, Carl (diciembre de 1996). "Historia de dos tamices" (PDF) . Avisos del AMS . 43 (12). págs. 1473-1485.
Otras lecturas
- Samuel S. Wagstaff, Jr. (2013). La alegría de la factorización . Providence, RI: Sociedad Matemática Estadounidense. págs. 143-171. ISBN 978-1-4704-1048-3.