# Continued Fractions Applied to the One Line Factoring Algorithm for Breaking RSA
## 4 Application to Breaking RSA250  
At the center of secure information transmission is the RSA cryptosystem. An information transmission scheme that meets a 128-bit security strength is widely accepted with a key size of approximately 3072 bits [24]. Even though high computing power is currently affordable with advancements in information and communication technologies, there are certain practical reasons for public key cryptographic schemes employing weak keys. One main reason for implementing weak key sizes is to ensure backward compatibility. Further, small key sizes are used in embedded environments with a scarcity of computational power for public-key cryptographic operations. Hence, several research studies assess the difficulty of the mathematical problem of prime factorization that underpins the security of RSA. They focus on the feasibility of integer factorization and the RSA factoring challenges thereof. A recent research study's target was the RSA240 factoring challenge [24], while previous records were related to breaking 768-bit keys [23,28]. RSA250 has 250 decimal digits (829 bits) and was only factored in 2020, which makes it a good candidate for exploring our method as it is of great research interest in the field of information security. In this paper, let us now consider RSA250 to apply our approach of factorization where we limit the search using the attributes \(P\) and \(Q\). We note that \(\frac{p}{Q}\) is known for RSA250 and hence the convergences for \(\frac{p}{q}\) are known. Let us consider the numbers given below for RSA250:  
\([\text{N}]\,21403246502407449612644230728393356300861475114475501797754920881418023\)\(444714013664334551909580467961092851872470914587687396261921557363047454770520805\)\(11905649310668769159001975940569345745223058932597669747168173806936489469987578\)\(494947593749739\)\([\text{P}]\,641352894707715802787901901705773890848250147429434472081168596320245324\)\(463023862359875266834770873661925586594639798853367\)\([\text{Q}]\,3337202759497815656526201060535511422794076034476755466678452098702384172\)\(92100370800257448673296881877565718986258036932062711\)  
The ratio \(P/Q\) is given by the continued fraction below and has a length of 261. The italicized and underlined part of the continued fraction provides the first suitable convergence for \(p/q\) which leads to a solution. \(\frac{1}{1}\,11\,11\,3\,1\,4\,2\,12\,6\,3\,1\,1\,1\,1\,1\,2\,6\,1\,4\,1\,4\,4\,4\, 7\,1\,3\,1\,1\,2\,3\,2\,1\,1\,7\,1\,4\,1\,1\,1\,5\,1\,1\,1\,1\,6\,1\,2\,5\)\(1\,1\,2\,3\,1\,2\,1\,1\,2\,7\,1\,3\,2\,1\,1\,2\,7\,1 1 4 4 1 4 4 3 1 29 1 12 3 17 1 1 1 11 1 36 36 2 1 8 14 1 7 5 2 1 3 1 8 16 19 1 6 9 1 3 2 1 1 1 2 1 1 4 2 2 2 1 1 1 4 1 3 1 1 4 2 2 17 1 4 2  
The 93 rd convergence produces a suitable \(k\) value which provides the solution for the factorization of RSA250 as given below:  
\([k,x,y,z]=\)  
\([204434212109703939500757143525262968326103010158225539227567282455007329593\)  
\(11323112\),  
\(6614798436316441172282844923498308148226213631865434648727190399017807486039\)  
\(13907394254563141547525634166624762339395539405514099746682174264049017168200037\)  
\(978399935\),  
\(63565612507432739868213955281603065344711254828495897407657403845305428771221\)  
\(668091\),  
\(0\)]. In the case of RSA250, the underlined part of the continued fraction convergence given above for the convergence of the ratio \(P/Q\) illustrates that, using our method, a convergence using only 93 of the 261 terms produces a suitable \(k\) value. \(k=2^{*}3\times 3\times 7\times 103\times 281\times 3407\times 72,907\times 157,733\times 334,993\times 26,532,262,619,089\)\(\times\)\(106,061,927,979,829\)\(\times\)\(113,832,765,910,030,508,110,732,786,883\). In RSA250, the representations of \(P\) and \(Q\) have the same number of decimal digits. Using this property and the value of \(\sqrt{\text{N}}\), a lower bound and an upper bound for possible \(k\) values can be determined [49]. The challenge is to find such a restricted search space for suitable \(k\) values.