निरंतर अंश गुणनखंडन

संख्या सिद्धांत में, निरंतर भिन्न गुणनखंड विधि (CFRAC) एक पूर्णांक गुणनखंड कलन विधि है। यह एक सामान्य-उद्देश्य वाला एल्गोरिदम है, जिसका अर्थ है कि यह किसी भी पूर्णांक 'एन' को फैक्टर करने के लिए उपयुक्त है, विशेष रूप या गुणों के आधार पर नहीं। इसका वर्णन डेरिक हेनरी लेहमर|डी द्वारा किया गया था। 1931 में एच. लेहमर और आर.ई. पॉवर्स, और 1975 में माइकल ए मॉरिसन और जॉन ब्रिलहार्ट द्वारा एक कंप्यूटर एल्गोरिदम के रूप में विकसित किया गया। निरंतर भिन्न विधि डिक्सन के गुणनखंड विधि पर आधारित है। यह के निरंतर भिन्न में [[अभिसरण (निरंतर अंश)]] का उपयोग करता है

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

चूँकि यह एक द्विघात अपरिमेय है, निरंतर अंश आवधिक निरंतर अंश होना चाहिए (जब तक कि n वर्गाकार न हो, जिस स्थिति में गुणनखंड स्पष्ट है)।

इसकी समय जटिलता है $O\left(e^{\sqrt {2\log n\log \log n}}\right)=L_{n}\left[1/2,{\sqrt {2}}\right]$, बिग ओ नोटेशन और एल अंकन नोटेशन में।

अग्रिम पठन

• Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. pp. 143–171. ISBN 978-1-4704-1048-3.