## 5 The Modular Segment LLL Reduction with Modular Arithmetic  
### Algorithm and Its Complexity  
We are now in a position to give our segment LLL reduction algorithm with modular arithmetic. It finds a segment LLL reduced basis with an \(O(n^{0.5})\) improvement in the computational complexity when \(M_{sc}=2^{O(n^{2})}\). This algorithm is given in Figure 12. The major difference in the **ModSegmentLLL** and **SegmentLLL** algorithms is in performing the **ModLocSegmentLL** step presented in Figure 13. In this subroutine we perform updates using modular arithmetic while working with \(\hat{B}\). The subroutines **ModReduce** and **ModSwap** require \(O(k)\) operations in comparison to the \(O(k^{2})\) worst case operations in the algorithm of [PERSON] described in the previous section. Figure 12: The Modular Segment LLL Basis Reduction. We now explain the steps in **ModLocSegmentLLL**. While working with the matrix \(\hat{B}\), let us partition  
\[T=\left[ \begin{array}{c|c|c}&A&\\ \hline&C&E\\ \hline&&\\ \hline&&&\end{array} \right]\]  
similar to the partitioning of \(\Gamma\) in (4.6). We perform two types of unimodular operations on \(\hat{B}\) in the **ModLocSegmentLLL** algorithm. The **Preprocess C** and **Postprocess C** steps are performed to ensure that the lattice basis vectors corresponding to \(C\) are size reduced before and after performing the **Local  
Figure 14: Size Reduction of a Segment Using Modular Arithmetic. Figure 13: The Modular Local Segment LLL Basis Reduction. \(\delta\)**-Reduction** step. This allows us to bound the size of matrix \(Q\) needed to update \(E\) after completing the **Local \(\delta\)-Reduction** step. The calls to **ModReduce** and **ModSwap** are as in the case of the **ModularLLL** algorithm with the important difference that they are now performed on a segment. **ModReduce** subtracts a multiple of a row (column) from another row (column). This unimodular operation is recorded by updating \(U_{l}\) modulo \(\beta\). The constant \(\beta\) used in the **ModSegmentLLL** algorithm is taken to be a multiple of \(M\). A choice of \(\beta\) is specified below in Lemma 4. This inferior value is used in the intermediate computations because during the algorithm we don't have a bound on the elements of \(\hat{B}\). However, the fact that the initial and terminating \(\hat{B}\) are size reduced ensures that a proper bound on \(\beta\) is still possible. The subroutine **ModSwap** performs all necessary computations to update \(C\) and \(U_{l}\) when two rows of \(\hat{B}\) are swapped. The elements of \(C\) are recorded modulo \(d_{i}d_{i-1}\beta\). As in the case of [PERSON]'s modification of the LLL algorithm, there is no need to record the modulo operations in \(U_{l}\). The matrix \(U_{l}\) is further updated in the **Postprocess C** step by incorporating all the unimodular transformations recorded in \(W\) while working on the size reduction of the basis vectors corresponding to \(C\). Here the elements of \(U_{l}\) are recorded modulo \(\beta\). Note that while \(U_{l}\) is recorded modulo \(\beta\), \(U\) is recorded modulo \(M\). Updating \(A\) and \(U\) is straightforward. In Section 5.2 we show that the computations involving \(U_{l}\) and \(A\) can be performed with integers of \(O(\ln M_{sc})\) bit length. To this end we use the results from [PERSON] [14] for his analysis of the semi-reduction algorithm. The total computational effort in Steps 1, 3, 4, and 5 of the **ModLocSegmentLLL** algorithm is \(O(nk^{2})\) arithmetic operations. Following [20] and [14, Theorem 18], there are at most \(n(\log_{1/\delta}M_{sc})\) swaps in all the executions of the **ModLocSegmentLLL** algorithm, each swap requiring \(O(k)\) arithmetic operations. Hence, we improve the total computational efforts in Step 2 [Modular Segment Iterations] of the **ModSegmentLLL** algorithm to \(O(nk\log_{1/\delta}M_{sc})\) arithmetic operations. Since there are a total of \(O(\frac{n}{k^{3}}\log_{1/\delta}M_{sc})\) calls to the **ModLocSegmentLLL** algorithm we are led to the following theorem.