# Improved Cryptanalysis of Some RSA Variants
## 3 Main Results
From this reduced matrix, we construct \(\omega\) polynomials \(r_{i}(x_{1},x_{2},x_{3},x_{4})\), where \(i=1,\ldots,\omega\), each of which satisfies the congruence  
\[r_{i}\Big{(}x_{1}^{(0)},x_{2}^{(0)},x_{3}^{(0)},x_{4}^{(0)}\Big{)}\equiv 0 \pmod{e^{\mu}}.\]  
In order to find the solution, we establish a connection between Theorems 1 and 2, concentrating on the scenario where \(j=4\). Thus, we set  
\[2^{\frac{\omega(\omega-1)}{4(\omega-3)}}\det(\mathcal{L})^{\frac{1}{\omega-3} }<\frac{e^{\mu}}{\sqrt{\omega}}.\]  
By combining with (2), this simplifies to  
\[e^{n_{e}-\mu(\omega-3)}X_{1}^{n_{X_{1}}}X_{2}^{n_{X_{2}}}X_{3}^{n_{X_{3}}}X_{4 }^{n_{X_{4}}}<\frac{1}{2^{\frac{\omega(\omega-1)}{4}}\big{(}\sqrt{\omega} \big{)}^{\omega-2}}<1. \tag{4}\]  
By considering the dominant terms in (3) along with the bounds in (1), and neglecting smaller values, we obtain  
\[\sigma\zeta^{2}+(\gamma+2\delta+4\sigma-4)\zeta+2\alpha+2\gamma+4\delta+4 \sigma-8<0, \tag{5}\]  
in which the optimal value for \(\zeta\) is  
\[\zeta_{0}=\frac{2-\delta-\frac{\gamma}{2}-2\sigma}{\sigma}.\]  
To ensure that \(\zeta_{0}>0\), the parameters must satisfy  
\[\delta+\frac{\gamma}{2}<2-2\sigma. \tag{6}\]  
Plugging \(\zeta_{0}\) in (5), we arrive at  
\[-4\delta^{2}-4(\gamma-4)\delta-\gamma^{2}+8\alpha\sigma+8\gamma-16<0.\]  
Solving the former inequation for \(\delta\), we obtain  
\[\delta<2-\sqrt{2\sigma\alpha}-\frac{\gamma}{2}.\]Using the assumption \(\alpha>2\sigma\) and (6), we obtain  
\[\delta+\frac{\gamma}{2}<\min\Bigl{(}2-\sqrt{2\sigma\alpha},2-2\sigma\Bigr{)}=2- \sqrt{2\sigma\alpha}.\]  
In addition, given that \(\delta\geq 0\) and \(\gamma\geq 0\), the inequality  
\[2-\sqrt{2\sigma\alpha}>0,\]  
is satisfied if \(\alpha<\frac{2}{\sigma}\). Afterward, we select four reduced and algebraically independent polynomials, denoted as \(r_{i}(x_{1},x_{2},x_{3},x_{4})\) for \(1\leq i\leq 4\). By solving the system of equations \(r_{i}(x_{1},x_{2},x_{3},x_{4})=0\) for \(i=1,2,3,4\) over the integers, using either the Grobner basis approach or resultant techniques, we can extract  
\[2^{\frac{\omega(\omega-1)}{4(\omega-3)}}\det(\mathcal{L})^{\frac{1}{\omega-3} }<\frac{e^{\mu}}{\sqrt{\omega}}.\]0  
Finally, solving the system \(N=pq\) and \(x_{2}^{(0)}+\tilde{p}+\tilde{q}=p+q\), we can recover \(p\) and \(q\). This concludes the proof. A consequence of Theorem 3 is the following result, which concerns the case where the modulus \(N=pq\) is the product of two primes, \(p\) and \(q\), with a sufficiently small difference \(|p-q|\). Corollary 1: _Let \((N,e)\) denote an RSA public key where \(N=pq\), with \(q<p<2q\), and \(e=N^{\alpha}\). Assume the existence of two parameters, \(|u|\leq N^{\delta}\) and \(|z|\leq N^{\gamma}\), such that \(eu\equiv z\pmod{\psi(N)}\), where \(\psi(N)=(p^{2}-1)(q^{2}-1)\). Furthermore, suppose that the prime difference \(|p-q|\leq N^{\sigma}\) is small, with \(0\leq\sigma\leq\frac{1}{2}\). If_  
\[2^{\frac{\omega(\omega-1)}{4(\omega-3)}}\det(\mathcal{L})^{\frac{1}{\omega-3} }<\frac{e^{\mu}}{\sqrt{\omega}}.\]1  
_then we can recover \(p\) and \(q\) in polynomial time._  
Proof: Assume that \(p-q<N^{\sigma}\). According to Lemma 1, we have \(q<\sqrt{N}<p\), which implies that  
\[2^{\frac{\omega(\omega-1)}{4(\omega-3)}}\det(\mathcal{L})^{\frac{1}{\omega-3} }<\frac{e^{\mu}}{\sqrt{\omega}}.\]2  
This suggests that \(\tilde{p}=\sqrt{N}\) is a close approximation of \(p\), with \(|p-\tilde{p}|<N^{\sigma}\). Applying Theorem 3, we can factor \(N=pq\) under the conditions  
\[2^{\frac{\omega(\omega-1)}{4(\omega-3)}}\det(\mathcal{L})^{\frac{1}{\omega-3} }<\frac{e^{\mu}}{\sqrt{\omega}}.\]3  
This completes the proof.