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

^ 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.
^ Morrison, Michael A.; Brillhart, John (January 1975). "A Method of Factoring and the Factorization of F₇". Mathematics of Computation. 29 (129). American Mathematical Society: 183–205. doi:10.2307/2005475. JSTOR 2005475.
^ Pomerance, Carl (December 1996). "A Tale of Two Sieves" (PDF). Notices of the AMS. Vol. 43, no. 12. pp. 1473–1485.

Read other articles:

Kazmabudug

Koordinat: 41°12′19″N 48°21′22″E / 41.20528°N 48.35611°E / 41.20528; 48.35611 KazmabudugKazmabudugKoordinat: 41°12′19″N 48°21′22″E / 41.20528°N 48.35611°E / 41.20528; 48.35611Negara AzerbaijanRayonQubaZona waktuUTC+4 (AZT) • Musim panas (DST)UTC+5 (AZT) Kazmabudug adalah sebuah desa di Rayon Quba, Azerbaijan. Referensi Kazmabudug pada GEOnet Names Server lbsRayon QubaIbu kota: Quba Adur Afurca Ağbil Alek...

Guerre seminole

Guerre seminoleVillaggio SeminoleData1817 - 1858 LuogoFlorida, Stati Uniti EsitoEsaurimento, con la maggior parte della tribù deportata in Oklahoma, e una parte minore rimasta libera nelle paludi fino ai giorni nostri[1] Schieramenti Stati UnitiSeminole Yuchi Choctaw Liberti Comandanti Andrew Jackson Martin Van Buren William Henry Harrison John Tyler Duncan Lamont Clinch Edmund P. Gaines Winfield Scott Thomas Jesup Richard Gentry † David Moniac † Francis Langhorne Dade † Zachar...

Battle of the Strait of Messina

Sea battle between Carthage and Pyrrhus (276 BC) For the medieval battle between Byzantines and Fatimids, see Battle of the Straits. 38°14′45″N 15°37′57″E / 38.24583°N 15.63250°E / 38.24583; 15.63250 Battle of the strait of MessinaPart of the Pyrrhic WarDate276 BCLocationStrait of MessinaResult Carthaginian victoryBelligerents Carthage Kingdom of EpirusCommanders and leaders Unknown Pyrrhus of EpirusStrength Unknown 110 warshipsCasualties and losses Unknown...

Free Four

Song by Pink Floyd Free FourCover of the 1972 Italy singleSingle by Pink Floydfrom the album Obscured by Clouds B-sideStayThe Gold It's in The...Released10 July 1972 (1972-07-10)RecordedFebruary–March 1972Strawberry Studios, FranceGenreFolk rock[1]Length4:15LabelHarvestSongwriter(s)Roger WatersProducer(s)Pink FloydPink Floyd singles chronology One of These Days (1971) Free Four (1972) Money (1973) Free Four is a song by the English rock band Pink Floyd, written by Rog...

威廉·莱昂·麦肯齐·金

威廉·莱昂·麦肯齐·金阁下The Rt Hon. William Lyon Mackenzie KingOM CMG PC 加拿大总理任期1921年12月29日—1926年6月28日君主乔治五世前任阿瑟·米恩继任阿瑟·米恩任期1926年9月25日—1930年8月7日君主乔治五世前任阿瑟·米恩继任理查德·贝德福德·贝内特任期1935年10月23日—1948年11月15日君主乔治五世爱德华八世乔治六世前任理查德·贝德福德·贝内特继任路易·圣洛朗个人资料出生...

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

Kamil Grosicki

Kamil Grosicki Nazionalità Polonia Altezza 180 cm Peso 75 kg Calcio Ruolo Centrocampista Squadra Pogoń Stettino CarrieraGiovanili Pogoń StettinoSquadre di club1 2005-2007 Pogoń Stettino23 (2)2007-2008 Legia Varsavia11 (1)2008-2009→ Sion8 (2)2009-2011 Jagiellonia57 (14)2011-2014 Sivasspor86 (13)[1]2014-2017 Rennes81 (13)2017-2020 Hull City133 (26)2020-2021 West Bromwich3 (0)2021- Pogoń Stettino81 (31)Nazionale 2005...

Ekspedisi Sumatra Pertama

Ekspedisi Sumatra PertamaBagian dari Ekspedisi SumatraInfanteri A.S. menyerang benteng Aceh di Kuala Batee pada tahun 1832Tanggal6–9 Februari 1832LokasiKuala Batee, Aceh, Hindia BelandaHasil Kemenangan Amerika SerikatPihak terlibat Amerika Serikat Belanda Tetua Kuala BateeTokoh dan pemimpin Komodor John Downes Gubernur Jenderal Johannes van den Bosch Raja Poh MuhammadKekuatan Darat:282 prajuritLaut:1 pergata Darat:~500 pejuang5 bentengLaut:3 perahuKorban 2 tewas11 terluka ~450 tewas at...

Tamaricaceae

Tamaricaceae Tamarix africana Klasifikasi ilmiah Kerajaan: Plantae (tanpa takson): Tracheophyta (tanpa takson): Angiospermae (tanpa takson): Eudikotil (tanpa takson): Eudikotil inti Ordo: Caryophyllales Famili: Tamaricaceae Link Genera Lihat teks Tamaricaceae atau Suku Tamariska-tamariskaan adalah salah satu suku anggota tumbuhan berbunga. Menurut Sistem klasifikasi APG II suku ini dimasukkan ke dalam bangsa Caryophyllales, klad dikotil sejati inti (core Eudikotil) namun tidak termasuk ke da...

Delight Mobile

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) The topic of this article may not meet Wikipedia's notability guidelines for companies and organizations. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the articl...

Joint Venture Protective Carbine

Type of submachine gun Modern Submachine Carbine/ Joint Venture Protective Carbine MSMC submachine gunTypeCarbinePlace of originIndiaService historyUsed bySee UsersProduction historyDesigned2005Manufacturer Advanced Weapons and Equipment India Limited (AWEIL) Kalyani Strategic Systems Limited (KSSL) Produced2005 – presentSpecificationsMass2.98 kg (6.6 lb) emptyLength552 mm (21.7 in) closed stock 745 mm (29.3 in) open stock[1]Barrel l...

Kaspar Villiger

Kaspar VilligerKaspar Villiger nel 2002 Presidente della Confederazione svizzeraDurata mandato1º gennaio 1995 –31 dicembre 1995 PredecessoreOtto Stich SuccessoreJean-Pascal Delamuraz Durata mandato1º gennaio 2002 –31 dicembre 2002 PredecessoreMoritz Leuenberger SuccessorePascal Couchepin Vicepresidente della Confederazione svizzeraDurata mandato1º gennaio 2001 –31 dicembre 2001 PresidenteMoritz Leuenberger PredecessoreMoritz Leuenberger Succe...

William Allan (trade unionist)

British trade unionist Allan in 1873 William Allan (August or September 1813 – 15 October 1874) was a British trade unionist. Born in Ulster, Allan grew up in Glasgow, working in a cotton mill from the age of twelve, then later serving an engineering apprenticeship. However, before completing the apprenticeship, he married and moved to Liverpool, soon finding work with the Grand Junction Railway Company. He later moved to Crewe to further his career, and while there joined the Mancheste...

Vià

French television network ViàTypeFree-to-air television networkCountryFranceLaunch dateJuly 4, 2018; 6 years ago (July 4, 2018) (ViàRéseau)[1] June 25, 2010; 14 years ago (June 25, 2010) (Médias du Sud)[2]Former namesTVSudOfficial websiteviaoccitanie.tvLanguageFrench Vià (stylised as vià) is a French television network. It started as a southern regional network in 2010,[2] before going national in 2018,[1] and subsequently contra...

Xe điện Dubai

Xe điện DubaiTập tin:Dubai Tram logo.pngXe điện tại Dubai MarinaTổng quanTiếng địa phươngترام دبيTình trạngHoạt độngSở hữuCơ quan Giao thông và Đường bộ (Dubai)Vị tríDubai, Các Tiểu vương quốc Ả Rập Thống nhấtGa đầuDubai MarinaGa cuốiAl SufouhNhà ga11 (19 theo kế hoạch)[1]Dịch vụHệ thốngXe điệnĐiều hànhSercoTrạm bảo trìAl SufouhLịch sửHoạt động11 tháng 11 năm 2014[2]Thông...

Good-Feel

Good-Feel Co., Ltd.JenisPrivateIndustriVideo game developer[1]Didirikan10 Maret 2005; 19 tahun lalu (2005-03-10)Kantor pusatKobe, Hyogo, JepangCabang2Tokoh kunciShigeharu Umezaki, PresidentEtsunobu Ebisu, Managing DirectorIsono Yoshikazu, DirectorProdukPermainan videoKaryawan96 (2017)Situs webwww.good-feel.co.jp Good-Feel Co., Ltd. (株式会社グッド・フィールcode: ja is deprecated , Kabushiki-Gaisha Guddo Fīru) adalah sebuah perusahaan pengembangan permainan video asal...

Aaron Hughes

Northern Irish footballer (born 1979) For the American Navy admiral, see Aaron K. Hughes. For the professor of Jewish studies, see Aaron W. Hughes. Aaron HughesMBE Hughes lining up for Northern Ireland in 2012Personal informationFull name Aaron William Hughes[1]Date of birth (1979-11-08) 8 November 1979 (age 44)[1]Place of birth Cookstown, Northern IrelandHeight 1.83 m (6 ft 0 in)[2]Position(s) DefenderYouth career1996–1998 Newcastle UnitedSenior ...

Invicta Ground

Former football stadium in Plumstead, London Invicta GroundFull nameInvicta GroundLocationPlumstead, London, EnglandOwnerGeorge WeaverCapacityc.12,000ConstructionOpened1890Closedc. 1894Demolished?TenantsWoolwich Arsenal (1890–1893)Royal Ordnance Factories (1893–1894) The Invicta Ground was a football stadium in Plumstead, south-east London, that was the home of club Royal Arsenal, now known as Arsenal. History Named after Invicta, the motto of the county of Kent, the ground was Arsenal's ...

Canting arms

Heraldric symbols representing the name of their owner, either literally or as a visual pun For the tool used for making batik, see Canting. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Canting arms – news · newspapers · books · scholar · JSTOR (August 2011) (Learn how and when to remove this message) A f...

كريستوف كوكارد

كريستوف كوكارد (بالفرنسية: Christophe Cocard)‏ معلومات شخصية الاسم الكامل كريستوف كوكارد الميلاد 23 نوفمبر 1967 (العمر 56 سنة)بيرناي الطول 1.77 م (5 قدم 9 1⁄2 بوصة) مركز اللعب الوسط الجنسية فرنسا مسيرة الشباب سنوات فريق إفرو المسيرة الاحترافية1 سنوات فريق مشاركات (أهداف...

PROFILPELAJAR.COM