# Continued Fractions Applied to the One Line Factoring Algorithm for Breaking RSA
## 2 Theory  
The theory on continued fractions and the history of various factorization methods form the back backbone of this research investigation. [PERSON]'s factorization method which was formulated in the early 1600's uses the difference of squares and was published much later [34; 35; 36]. However, most modern factorization algorithms are based on [PERSON]'s factorization method [37; 38; 39; 40]. In the 1920s, [PERSON] presented a notable improvement to [PERSON]'s factorization. Instead of having a number \(n\) as a difference of squares, [PERSON] determined that it would suffice to find a difference of squares equal to a multiple of \(N\)[41]. This can be mathematically stated as \(X^{2}\equiv Y^{2}\ mod\ N\). In 1985, Pomerance's Quadratic Factoring Algorithm [19] used [PERSON]'s scheme with the steps given below:  
1. Generate congruences \(U\equiv V\ mod\ N\). 2. Determine factorizations of \(U\) and \(V\) for some of the congruences. 3. Determine a subset of the factored congruences which, when multiplied, produce a special congruence \(X^{2}\equiv Y^{2}\ mod\ N\). 4. Factorization of \(N:\gcd(X-Y,N)\). Consider \(X^{2}\equiv Y^{2}\ mod\ N\). This can be rewritten as given below: 1. \(X^{2}-Y^{2}\equiv 0\ mod\ N\). 2. \(X^{2}-Y^{2}=kN\). 3. \((X-Y)(X+Y)=kN\). 4. \(P=\gcd(X-Y,kN)\) or \(Q=\gcd(X+Y,kN)\). Our premise is that if we can find such a solution as mathematically derived in the above steps, then the greatest common divisor (gcd) will be a solution to the factorization of \(N:N=PQ\). We carefully consider [PERSON]'s work of 1981, which states that attempting to factorize a semi-prime \(N=PQ\) with \(4 kN\) \"is a rather curious way to proceed, if not down right stupid\" [42]. Further, according to [PERSON], finding \(k\) is clearly a chicken and egg scenario. In this work, we aim to perform experiments to investigate the characteristics of \(k\) by working backwards from the answer and narrowing the search field for possible \(k\) values. Further, we study many correct solutions which are the convergences of \(PQ\), which have not been explored previously. We believed that this ongoing research work would lead to interesting findings and make better use of our narrower definition of the parameterization of \(k\). We next provide a brief background of related articles and their evolution in this domain. Continued Fraction Factorization (CFRAC) is well defined among factorization algorithms and is the baseline against which all others are measured. In number theory, the CFRAC method was the first general-purpose factorization algorithm that was efficiently implemented in 1975 as a computer algorithm by [PERSON] and [PERSON] [7] using the continued fraction approach of \(\sqrt{kN}\). A few years later, [PERSON] and [PERSON] explored this further and considered in detail the Knuth-Schroeppel function, which attempted to find suitable values for \(k\) that generated new ideas for factoring large integers [43, 44]. Subsequently, [PERSON] and [PERSON] provided a computational history of factoring and the refinement of several ideas in this space [45]. While such combinations of number theory ideas have their mathematical merits, in this paper, our interest lies in finding a more simple and elegant approach that can motivate many researchers from the information security domain to explore further in this direction. We focus on the initial work published in 1974 by [PERSON], who considered the ratio of \(\frac{P}{Q}\) as \(\frac{g}{b}\) such that \(x^{2}-y^{2}=4 kN,k=ab\)[46]. After nearly four decades, [PERSON] considered [PERSON]'s work and ideas from [PERSON]'s method (SQUFOF) reported in 1982 [31] and subsequently developed a one line factoring algorithm in 2012 [32]. From the above equation provided in (2), namely \(X^{2}-Y^{2}=kN\), we obtain  
\[Y^{2}=X^{2}-kN\text{. If we let }X=\left\lceil\sqrt{kN}\right\rceil\text{, then }Y^{2}=\left(\left\lceil\sqrt{kN}\right\rceil\right)^{2}-kN\text{.}\]  
Our simple approach looks for a \(k\) value which provides a perfect square.