# Continued Fractions Applied to the One Line Factoring Algorithm for Breaking RSA
## 3 Worked Examples  
We provide the verified working of our factorization approach using two worked examples in this section. In the first example, we consider an integer (13,290,059) to factorize using continued fractions. This can be achieved with a brute force search by incrementing through \(k\) until \(k=4 pq\ \Rightarrow\ p/q=11/8\). This provides us with a factorization of 13,290,059 with factors \(P=4261\) and \(Q=3119\). Let us now consider the solution and describe the ratio of \(P/Q\) as a continued fraction such that \(4261/3119\Rightarrow\)\(>1\ 2\ 1\ 2\ 1\ 2\ 1\ 1\ 3\ 12\). We will now consider each convergent fraction of the continued fraction in turn until we find a \(k\) value which provides a solution to \(x^{2}-y^{2}=kN,k=4 pq\). Using our approach, the fourth convergence for \(4261/3119\Rightarrow\)\(>1\ 2\ 1\ 2\ 1\ 2\ 1\ 1\ 3\ 12\) provides the solution. The first four convergences are indicated by [k,x,y,z]. Note that when \(z=0\), a solution is found. 1. \(\frac{p}{q}=\frac{1}{1}\Rightarrow[k,\ x,\ y,\ z]=[4,\ 7292,\ 114,\ 5]\). 2. \(\frac{p}{q}=\frac{3}{2}\Rightarrow[k,\ x,\ y,\ z]=[24,\ 17860,\ 134,\ 15]\). 3. \(\frac{p}{q}=\frac{4}{3}\Rightarrow[k,\ x,\ y,\ z]=[48,\ 25258,\ 209,\ 7]\). 4. \(\frac{p}{q}=\frac{11}{8}\Rightarrow[k,\ x,\ y,\ z]=[352,\ 68397,\ 221,\ 0]\). For the example considered here, we arrive at \(gcd(68397-221,13290059)=4261\). From the above, it can be verified easily that the fourth convergence finds the factors as the solution for this example. We note that all other convergences after this one also provide suitable values for \(k\) that lead to a solution. Other approaches such as [PERSON]'s method require many polynomials to generate the residues [47]. As a second example, we consider the integer \(21,565,941,721,999,797,939,843,713,963\), a 95-bit prime number as illustrated by [PERSON] and Pomerance [48] on pg307. To factorize using continued fractions, the solution can be achieved with a brute force search by incrementing through \(k\) until the following value is reached:  
\[k=4 pq\ \ \Rightarrow\ \ p/q=17887/6172\]  
This obtains a factorization of 21,565,941,721,999,797,939,843,713,963 with factors \(P=10000000000000037\) and \(Q=21565941721999\). Consider the solution describing the ratio of \(P/Q\) as a continued fraction such that 1,000,000,000,000,037/21,565,941,721,999 \(\Rightarrow\ \frac{46}{2}\ 1\ 2\ 2\ 2\ 2\ 1\ 1\ 1\ 3\ 8\ 13\ 1\ 263\ 1\ 5\ 38\ 1\ 4\) 1 2 2 8 2 1 1 2. The continued fraction length is 26 and, by applying our approach, the 11 th convergence provides a suitable \(k\) value and the resulting factorization shown below:  
1. \(\frac{p}{q}=\frac{46}{1}\Rightarrow[k,\ x,\ y,\ z]=[184,\ 1992017388691164,\ 33696672,\ 4942]\). 2. \(\frac{p}{q}=\frac{93}{2}\Rightarrow[k,\ x,\ y,\ z]=[744,\ 4005628619975628,\ 66115834,\ 9235]\). 3. \(\frac{p}{q}=\frac{139}{3}\Rightarrow[k,\ x,\ y,\ z]=[1668,\ 5997665445179121,\ 26939199,\ 4084]\). 4. \(\frac{p}{q}=\frac{371}{8}\Rightarrow[k,\ x,\ y,\ z]=[11872,\ 16000964349800346,\ 91024971,\ 12000]\). 5. \(\frac{p}{q}=\frac{881}{19}\Rightarrow[k,\ x,\ y,\ z]=[66956,\ 3799959465491991,\ 84176579,\ 1177]\). 6. \(\frac{p}{q}=\frac{2133}{46}\Rightarrow[k,\ x,\ y,\ z]=[392472,\ 92000153692897192,\ 370945991,\ 18331]\). 7. \(\frac{p}{q}=\frac{5147}{117}\Rightarrow[k,\ x,\ y,\ z]=[2285268,\ 221999902043111349,\ 519272009,\ 23683]\). 8. \(\frac{p}{q}=\frac{7280}{157}\Rightarrow[k,\ x,\ y,\ z]=[4571840,\ 314000055736153583,\ 655378625,\ 20303]\). 9. \(\frac{p}{q}=\frac{1242}{268}\Rightarrow[k,\ x,\ y,\ z]=[13321744,\ 53999577 7289827,\ 662310841,\ 18309]\). \(\frac{p}{q}=\frac{19707}{425}\Rightarrow\ [k,\ x,\ y,\ z]=[33501900,\ 850000013515449911,\ 875520517,\ 15650]\). 11. \(\frac{p}{q}=\frac{71548}{1543}\Rightarrow\ [k,\ x,\ y,\ z]=[441594256,\ 3085999998325641543,\ 1674472639,\ 0]\).