Continued fraction factorization

In number theory, the continued fraction factorization method (CFRAC) is an integer factorization algorithm. It is a general-purpose algorithm, meaning that it is suitable for factoring any integer n, not depending on special form or properties. It was described by D. H. Lehmer and R. E. Powers in 1931,^[1] and developed as a computer algorithm by Michael A. Morrison and John Brillhart in 1975.^[2]

The continued fraction method is based on Dixon's factorization method. It uses convergents in the regular continued fraction expansion of

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

Since this is a quadratic irrational, the continued fraction must be periodic (unless n is square, in which case the factorization is obvious).

It has a time complexity of $O\left(e^{\sqrt{2\log n \log\log n}}\right)=L_n\left[1/2,\sqrt{2}\right]$, in the O and L notations.^[3]

References

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 (January 1975). "A Method of Factoring and the Factorization of F₇". Mathematics of Computation (American Mathematical Society) 29 (129): 183–205. doi:10.2307/2005475. JSTOR 2005475. 
3. ^ Pomerance, Carl (December 1996). "A Tale of Two Sieves". Notices of the AMS 43 (12): pp. 1473–1485. http://www.ams.org/notices/199612/pomerance.pdf 

This number theory-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Integer factorization algorithms Number theory stubs Wikimedia Foundation. 2010. Игры ⚽ Нужно сделать НИР? Tan Cheng Lock Henry Hastings, 3rd Earl of Huntingdon Look at other dictionaries: Integer factorization — In number theory, integer factorization is the way of breaking down a composite number into smaller non trivial divisors, which when multiplied together equal the original integer.When the numbers are very large, no efficient integer… …   Wikipedia List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia Congruence of squares — In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms. Derivation Given a positive integer n, Fermat s factorization method relies on finding numbers x, y satisfying the equality We can then… …   Wikipedia John Brillhart — John David Brillhart is a mathematician, professor emeritus at the University of Arizona. He is known for his work in integer factorization, including the development of the continued fraction factorization method. [cite journal|last =… …   Wikipedia John Brillhart — John David Brillhart (* 13. November 1930 in Alameda County, Kalifornien) ist ein US amerikanischer Mathematiker, der sich mit Algorithmischer Zahlentheorie beschäftigt. Brillhart studierte an der University of California, Berkeley, wo er 1967… …   Deutsch Wikipedia R. E. Powers — Details of the life of R.E. Powers are little known; however, he was apparently the first mathematician to demonstrate that the Mersenne number M107 = 2107 − 1 was indeed prime. This was published in his article Certain composite Mersenne s… …   Wikipedia Факторизация целых чисел — Факторизацией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики. В отличие от… …   Википедия List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia Factorial — n n! 0 1 1 1 2 2 3 6 4 24 5 120 6 720 7 …   Wikipedia Square root of 5 — The square root of 5 is the positive real number that, when multiplied by itself, gives the prime number 5. This number appears in the formula for the golden ratio. It can be denoted in surd form as::sqrt{5}.It is an irrational algebraic number.… …   Wikipedia 18+ © Academic, 2000-2023 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”