## 5 The Modular Segment LLL Reduction with Modular Arithmetic
### Correctness of the **ModSegmentLLL** Algorithm  
The following lemma allows us to compute \(U\) modulo \(M\), and \(T\) modulo \(d_{i}d_{i-1}M\) during the **ModSegmentLLL** algorithm. **Lemma 3**: _Upon termination, the reduced basis from the_ **SegmentLLL** _and_ **ModSegmentLLL** _algorithms has the following upper bound_  
\[\|b_{i}\|^{2}\leq nM_{0}\ \mathrm{for}\ 1\leq i\leq n,\ \mathrm{and}\ \|b_{i}^{*}\|\leq M_{0}\]  
_throughout the algorithm._  
**Proof:** Follow the proof of Lemma 2, while observing that size reduction or modular reduction of the elements in \(T\) leave \(\|b_{i}^{*}\|\) unchanged. \(\square\)  
The following lemma of [PERSON] allows to give a proper value of \(\beta\), which is used to reduce the entries of \(U_{l}\) and \(C\) modulo \(\beta\). We now show that \(U_{l}\), \(A\), \(C\), and \(E\) are correctly updated using integers of \(O(\ln M_{sc})\) bits. **Lemma 4**: _[_8_]_ _Let \(\hat{B}_{\text{leg}}\), \(\hat{B}_{\text{end}}\in\mathbb{Z}^{2k\times d}\) be size-reduced bases. The unimodular matrix \(\hat{U}\) that transforms \(\hat{B}_{\text{leg}}\) to \(\hat{B}_{\text{end}}\) satisfies_  
\[\|\hat{U}\|_{1}\leq(2k)^{2}(\frac{3}{2})^{2k-1}M_{sc}\leq M_{sc}^{2}\]  
_where \(\|\hat{U}\|_{1}=\max_{j}\{\|\hat{U}_{j}^{t}\|_{1}\}\) and \(\hat{U}_{j}^{t}\) is the \(j\)-th column of \(\hat{U}\)._  
Lemma 4 allows to take \(\beta=q_{\beta}M\), where \(q_{\beta}=[(2\lceil M_{sc}^{2}\rceil+1)/M]+1\) while reducing the entries of \(U_{l}\) modulo \(\beta\). Note that taking \(\beta\) as a multiple of \(M\) is important because \(U_{l}\) is used to update U whose elements are computed modulo M.  
Updating \(E\)  
Let \(R\) be the \(2k\times 2k\) diagonal matrix with the \(i\)-th diagonal entry \(d_{k(l-1)+i}d_{k(l-1)+i-1}\) for \(1\leq i\leq 2k\), and \(H\) the \(2k\times 2k\) diagonal matrix with \(H_{1,1}=(C_{new})_{1,1}d_{k(l-1)}\) and \(H_{i,i}=(C_{new})_{i,i}(C_{new})_{i-1,i-1}\) for \(2\leq i\leq 2k\), where \(d_{k(l-1)+i},1\leq i\leq 2k\) are the diagonal entries of \(C_{\text{leg}}\). Following [PERSON]'s development of his algorithm for finding a semi-reduced basis in [14, Equation (29)], we can show that the matrix \(E\) is updated by  
\[\tilde{E}=QE,\ \text{where}\ Q=\frac{1}{d_{k(l-1)}}H(C_{new}^{-1})^{t}U_{l}d_{ k(l-1)}C_{\text{leg}}^{t}R^{-1}\]  
These computations are performed in a specific order to maintain integrality of operations: (i) backtrack fraction free Gaussian elimination by pre-multiplying \(E\) by \(d_{k(l-1)}C_{\text{leg}}^{t}R^{-1}\); (ii) pre-multiply by the basis modular transformation matrix \(U_{l}\); (iii) forwardtrack fraction free Gaussian elimination by pre-multiplying the result from (ii) by \((1/d_{k(l-1)})H(C_{new}^{-1})^{t}\). To establish a bound on the magnitudes of the integers in \(\tilde{E}\), we need to bound \(\|C_{new}^{-1}\|_{\infty}\). Let \(S\) be the \(2k\times 2k\) diagonal matrix with the \(i\)-th diagonal entry \((C_{new})_{i,i}\) for \(1\leq i\leq 2k\) so that \(S^{-1}C_{new}\) is unit upper triangular with all off diagonal entries \(\leq 1/2\), (Recall that the basis vectors corresponding toare size-reduced). In particular, the entries in \((S^{-1}C_{new})^{-1}\) are \(2k\times 2k\) minors of \((S^{-1}C_{new})\) which is bounded by \((2k)^{k}\) using [PERSON]'s inequality. It follows that the entries in \(C_{new}^{-1}=(S^{-1}C_{new})^{-1}S^{-1}\) are bounded by \((2k)^{k}\) because \(d_{i}\geq 1,1\leq i\leq n\). We get  
\[\|\tilde{E}\|_{\infty}=\|QE\|_{\infty} \leq(2k)^{3}\|H\|_{\infty}\|C_{new}^{-1}\|_{\infty}\|U_{l}\|_{ \infty}\|C_{beg}^{t}\|_{\infty}\beta\] \[\leq(2k)^{3}M_{sc}^{2}(2k)^{k}(2k)^{2}(3/2)^{2k-1}M_{sc}M_{sc}\beta\] \[\leq 2(2k)^{k+5}(3/2)^{2k-1}M_{sc}^{6} \tag{5.7}\]  
The above inequality shows that the entries of \(\tilde{E}\) are bounded by \(O(\ln M_{sc}+k\ln k)\) bit length. Furthermore, if \(\tilde{E}\) is computed by multiplying \(E\) with matrices in \(Q\) from right to left, then all intermediate matrices are fraction free, and the computations are performed on integers of size \(O(\ln M_{sc})\).