# Improved Cryptanalysis of Some RSA Variants
## 2 Preliminaries
### Lattice Reduction and Coppersmith's Technique  
Lattices are fundamental mathematical structures that play a crucial role in various branches of mathematics. They can be understood as discrete subgroups of finite-dimensional vector spaces. Formally, a Euclidean lattice is defined as follows:  
**Definition 1**. : _Let \(\mathbf{u}_{1},\mathbf{u}_{2},\ldots,\mathbf{u}_{\omega}\in\mathbb{R}^{d}\) be \(\omega\) linearly independent vectors with \(\omega\leq d\). The Euclidean lattice spanned by \(\{\mathbf{u}_{1},\mathbf{u}_{2},\ldots,\mathbf{u}_{\omega}\}\) is the set_  
\[\mathcal{L}=\mathbb{Z}\mathbf{u}_{1}+\mathbb{Z}\mathbf{u}_{2}+\cdots+\mathbb{ Z}\mathbf{u}_{\omega}.\]_The collection \(\{\mathbf{u}_{1},\mathbf{u}_{2},\ldots,\mathbf{u}_{\omega}\}\) is termed a basis for the lattice \(\mathcal{L}\), with \(\omega\) and \(d\) corresponding to the rank and dimension of the lattice, respectively. When \(\omega=d\), the lattice \(\mathcal{L}\) is said to have full rank._  
A matrix representation of a lattice \(\mathcal{L}\) can be described as follows: Let \(\mathcal{B}\in\mathbb{R}^{\omega\times d}\) be the matrix whose rows correspond to the basis \(\{\mathbf{u}_{1},\mathbf{u}_{2},\ldots,\mathbf{u}_{\omega}\}\). Then, an element \(\mathbf{v}\) belongs to \(\mathcal{L}\) if, and only if, there exists \(\mathbf{x}\in\mathbb{Z}^{\omega}\) such that \(\mathbf{v}=\mathbf{x}\mathcal{B}\). The quantity defined by \(\det(\mathcal{L})=\sqrt{\det(\mathcal{B}^{t}\mathcal{B})}\) is referred to as the determinant of the lattice, where \(\mathcal{B}^{t}\) denotes the transpose of the basis matrix \(\mathcal{B}\). For a lattice of full rank, the determinant simplifies to the form \(\det(\mathcal{L})=|\det(\mathcal{B})|\). It is a known fact that a lattice \(\mathcal{L}\) of rank \(\omega\geq 2\) has infinitely many bases, each consisting of \(\omega\) vectors and having an identical determinant. Nevertheless, identifying a basis made up of short vectors is a computationally difficult task, particularly as the lattice dimensions grow. In 1982, [PERSON], [PERSON], and [PERSON] [PERSON] and [PERSON] (2000) proposed the LLL algorithm, a polynomial-time method for computing a reduced basis with relatively short vectors. The following theorem, derived from [PERSON] and [PERSON] (2000), outlines the properties of a reduced basis generated by the LLL algorithm:  
**Theorem 1**. : _For any lattice \(\mathcal{L}\subseteq\mathbb{R}^{d}\) defined by a basis \(\{\mathbf{u}_{1},\mathbf{u}_{2},\ldots,\mathbf{u}_{\omega}\}\). The LLL algorithm produces a reduced basis \(\{\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{\omega}\}\), such that_  
\[\|\mathbf{v}_{1}\|\leq\|\mathbf{v}_{2}\|\leq\cdots\leq\|\mathbf{v}_{j}\|\leq 2 ^{\frac{\omega(\omega-1)}{4(\omega+1-j)}}\det(\mathcal{L})^{\frac{1}{\omega+1- j}}.\]  
_for every \(j=1,\ldots,\omega\)._  
Prior to 1996, polynomials of the form \(P(z)\equiv 0\pmod{M}\) were typically solved when the modulus \(M\) had a known factorization, employing techniques like the Chinese Remainder Theorem and the properties of finite fields. In 1996, [PERSON] (1996) presented an innovative approach for determining small roots of modular polynomial equations of the form  
\[P(z)\equiv 0\pmod{M},\]  
even when the factorization of the modulus \(M\) was not available. This breakthrough was extended to multivariate polynomials, which are expressed as  
\[P(z_{1},z_{2},\ldots,z_{n})=\sum_{i_{1},i_{2},\ldots,i_{n}}\rho_{i_{1},i_{2}, \ldots,i_{n}}z_{1}^{i_{1}}z_{2}^{i_{2}}\ldots z_{n}^{i_{n}},\]  
where \(\rho_{i_{1},i_{2},\ldots,i_{n}}\in\mathbb{Z}\). The Euclidean norm related to this polynomial is expressed as  
\[\|P(z_{1},z_{2},\ldots,z_{n})\|=\sqrt{\sum_{i_{1},i_{2},\ldots,i_{n}}\rho_{i_{ 1},i_{2},\ldots,i_{n}}^{2}}.\]  
In 1997, [PERSON] (1997) revisited [PERSON]'s technique and proposed a new technique for finding small roots. This advance provided a key result that became foundational in the field. **Theorem 2** (Howgrave-Graham).