# Improved Cryptanalysis of Some RSA Variants
## 3 Main Results
In addition to \(\left|x_{2}^{(0)}\right|<2N^{\sigma}\), the corresponding bounds are given by  
\[2\sigma<\alpha<\frac{2}{\sigma}\quad\text{and}\quad\delta+\frac{\gamma}{2}<2- \sqrt{2\sigma\alpha},\]8Next, we construct the lattice \(\mathcal{L}\) represented by the matrix whose rows consist of the coefficient vectors of the polynomials \(G_{w,a,b}(X_{1}x_{1},X_{2}x_{2},X_{3}x_{3},X_{4}x_{4})\). A lower triangular matrix can be formed by considering the following criteria: The rows of this matrix correspond to the polynomials \(G_{w,a,b}(X_{1}x_{1},X_{2}x_{2},X_{3}x_{3},X_{4}x_{4})\) and are arranged lexicographically, assuring that  
\[2\sigma<\alpha<\frac{2}{\sigma}\quad\text{and}\quad\delta+\frac{\gamma}{2}<2- \sqrt{2\sigma\alpha},\]9  
if \(w<w^{\prime}\), or if \(w=w^{\prime}\) and \(a<a^{\prime}\), or if \(w=w^{\prime}\), \(a=a^{\prime}\), and \(b<b^{\prime}\). Similarly, the columns are represented by the monomials \(x_{1}^{a}x_{2}^{b}x_{3}^{\mu-a-w}x_{4}^{w}\), and the lexicographical ordering is as follows:  
\[|q-\tilde{q}|<N^{\sigma},\quad|p+q-\tilde{p}-\tilde{q}|<2N^{\sigma}.\]0  
if \(w<w^{\prime}\), or if \(w=w^{\prime}\) and \(a<a^{\prime}\), or if \(w=w^{\prime}\), \(a=a^{\prime}\), and \(b<b^{\prime}\). A typical example of the lattice basis matrix for \(\mu=\zeta=2\) and  
\[|q-\tilde{q}|<N^{\sigma},\quad|p+q-\tilde{p}-\tilde{q}|<2N^{\sigma}.\]1  
using \(x_{1}x_{2}^{2}=x_{3}+x_{4}\), is provided in \[|q-\tilde{q}|<N^{\sigma},\quad|p+q-\tilde{p}-\tilde{q}|<2N^{\sigma}.\]2 The symbol \(\star\) marks the non-zero entries. By construction, the lattice basis matrix is lower triangular, and each diagonal entry takes the form \(X_{1}^{a}X_{2}^{b}X_{3}^{\mu-a-w}X_{4}^{w}e^{\mu-w}\) for some combination \((w,a,b)\) belonging to \(\mathcal{C}\cup\mathcal{D}\). This shows that the determinant of the lattice can be expressed as  
\[|q-\tilde{q}|<N^{\sigma},\quad|p+q-\tilde{p}-\tilde{q}|<2N^{\sigma}.\]3  
with \(n_{X_{1}}=\mathcal{E}(a)\), \(n_{X_{2}}=\mathcal{E}(b)\), \(n_{X_{3}}=\mathcal{E}(\mu-a-w)\), \(n_{X_{4}}=\mathcal{E}(w)\), \(n_{e}=\mathcal{E}(\mu-w)\), and  
\[|q-\tilde{q}|<N^{\sigma},\quad|p+q-\tilde{p}-\tilde{q}|<2N^{\sigma}.\]4  
\begin{table}
\begin{tabular}{l c c c c c c c c c c c} \hline \hline \(G_{w,a,b}\) & \(x_{3}^{2}\) & \(x_{1}x_{3}\) & \(x_{1}x_{2}x_{3}\) & \(x_{1}^{2}\) & \(x_{1}^{2}x_{2}\) & \(x_{3}x_{4}\) & \(x_{2}x_{3}x_{4}\) & \(x_{1}x_{4}\) & \(x_{1}x_{2}x_{4}\) & \(x_{4}^{2}\) & \(x_{2}x_{4}^{2}\) & \(x_{2}^{2}x_{4}^{2}\) \\ \hline \(G_{0,0,0}\) & \(e^{2}X_{3}^{2}\) & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \(G_{0,1,0}\) & 0 & \(e^{2}X_{1}X_{3}\) & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \(G_{0,1,1}\) & 0 & 0 & \(e^{2}X_{1}X_{2}X_{3}\) & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \(G_{0,2,0}\) & 0 & 0 & 0 & \(e^{2}X_{1}^{2}\) & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \(G_{0,2,1}\) & 0 In order to optimize \(\zeta\), we replace it with \(\mu\zeta\), and to facilitate the computations, we adopt the approximation \(\lfloor x\rfloor\approx x\) for a real number \(x\). Consequently, the exponents \(n_{X_{1}}\), \(n_{X_{2}}\), \(n_{X_{3}}\), \(n_{X_{4}}\), \(n_{e}\), along with the lattice dimension \(\omega=\mathcal{E}(1)\), are governed by the following relations:  
\[ \begin{split} n_{X_{1}}&=\frac{1}{3}\mu^{3}+o(\mu^{ 3})\\ n_{X_{2}}&=\frac{1}{6}\zeta^{2}\mu^{3}+o(\mu^{3}) \\ n_{X_{3}}&=\frac{1}{6}(\zeta+2)\mu^{3}+o(\mu^{3}) \\ n_{X_{4}}&=\frac{1}{3}(\zeta+1)\mu^{3}+o(\mu^{3}) \\ n_{e}&=\frac{1}{6}(\zeta+4)\mu^{3}+o(\mu^{3}) \\ \omega&=\frac{1}{2}(\zeta+2)\mu^{2}+o(\mu^{2}). \end{split}  \tag{3}\]  
The LLL algorithm is applied to reduce the matrix \(M\), yielding a reduced matrix \(M^{\prime}\) that preserves the determinant.