В теории чисел , то метод факторизации цепной дроби ( CFRAC ) представляет собой целое число , разложение алгоритм . Это универсальный алгоритм, что означает, что он подходит для факторизации любого целого числа n , независимо от специальной формы или свойств. Он был описан Д.Х. Лемером и Р. Э. Пауэрсом в 1931 г. [1] и разработан как компьютерный алгоритм Майклом А. Моррисоном и Джоном Брилхартом в 1975 г. [2]
Метод непрерывной дроби основан на методе факторизации Диксона . Он использует дроби в регулярном расширении цепной дроби из
- .
Поскольку это квадратичный иррациональный , непрерывная дробь должна быть периодической (если n не является квадратом, и в этом случае факторизация очевидна).
Он имеет временную сложность , в O и L обозначений. [3]
![O \ left (e ^ {{{\ sqrt {2 \ log n \ log \ log n}}}} \ right) = L_ {n} \ left [1/2, {\ sqrt {2}} \ right]](https://wikimedia.org/api/rest_v1/media/math/render/svg/d252c7723eefcda234a20f8c89f10bd0ed364a5d)
Ссылки [ править ]
- ^ Lehmer, DH; Пауэрс, RE (1931). «О факторинге больших чисел» . Бюллетень Американского математического общества . 37 (10): 770–776. DOI : 10.1090 / S0002-9904-1931-05271-X .
- ^ Моррисон, Майкл А .; Бриллхарт, Джон (январь 1975). «Метод факторинга и факторизация F 7 » . Математика вычислений . Американское математическое общество. 29 (129): 183–205. DOI : 10.2307 / 2005475 . JSTOR 2005475 .
- ^ Померанс, Карл (декабрь 1996). «Сказка о двух решетах» (PDF) . Уведомления AMS . 43 (12). С. 1473–1485.
Дальнейшее чтение [ править ]
- Сэмюэл С. Вагстафф младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. С. 143–171. ISBN 978-1-4704-1048-3.
