## 4 The Segment LLL Reduction of Lattice Bases  
Recently [PERSON] and [PERSON] [20] introduced the concept of a segment LLL reduced basis (See Definition **D7**), and gave an algorithm for finding such a basis. The segment LLL reduced basis satisfies a slightly weaker condition, however, it is computed by [PERSON] and [PERSON] [20] in \(O(n)\) fewer arithmetic operations. The algorithm of [PERSON] and [PERSON] works on two segments of \(B\), _i.e._, \([B_{l-1},B_{l}]=[b_{k(l-1)+1},\ldots,b_{k(l+1)}]\) at a time. This algorithm is outlined in Figure 10. The work in the **SegmentLLL** algorithm comes from the calls to a subroutine **Loc-LLL**(\(l\)) given in Figure 11. Subroutine **Loc-LLL**(\(l\)) performs a local LLL basis reduction on the segment [\(B_{l-1},B_{l}\)] and records the operations in a unimodular matrix \(U_{l}\in\mathbb{Z}^{2k\times 2k}\), as explained below.  
The Local-LLL reduction (Subroutine **Loc-LLL**(\(l\))) works on \(\hat{B}:=[B_{l-1},B_{l}]^{t}\) and \(\Gamma\). The matrix \(\Gamma\) in (4.6) is partitioned into segments with each segment has \(2k\) basis vectors.  
Figure 10: The Segment LLL Basis Reduction Algorithm.  
When working in **Loc-LLL(\(l\))** all LLL swaps and size reductions are restricted to the input \(2k\) segment. Only the matrix \(\Gamma_{C}\) is updated while performing the segment LLL swaps and size reductions. The unimodular operations updating \(\Gamma_{A}\), and the operations required to update \(\Gamma_{E}\) are stored in the matrix \(U_{l}\). The updates for \(\Gamma_{A}\) and \(\Gamma_{E}\) are performed only after it is no longer possible to perform an LLL-swap based on the information in \(\Gamma_{C}\). \(\Gamma_{A}\) and \(\Gamma_{E}\) are updated as follows:  
\[\Gamma_{A}=\Gamma_{A}U_{l},\ \ \Gamma_{E}=(\Gamma_{C})_{end}U_{l}^{-1}(\Gamma_{C}) _{beg}^{-1}\Gamma_{E}\]  
Here \((\Gamma_{C})_{beg}\) and \((\Gamma_{C})_{end}\) are \(\Gamma_{C}\) matrices recorded at the beginning and end of the **Local LLL-reduction** step in **Loc-LLL(\(l\))**. Since only matrix \(\Gamma_{C}\) is updated during the LLL unimodular operations in this segment the corresponding updates of \(\Gamma_{C}\) and \(U_{l}\) are performed using \(O(k^{2})\) arithmetic operations. The total number of swaps in all calls to **Loc-LLL(\(l\))** is bounded by \(O(n\log_{1/\delta}M_{sc})\), hence the total work in the **Local LLL-reduction** step is bounded by \(O(nk^{2}\log_{1/\delta}M_{sc})\) arithmetic operations.  
Figure 11: The Local LLL Iterations.  
The cost of updating \(\Gamma_{A}\) and \(\Gamma_{C}\), and performing the **Segment Size Reduction** step in each execution of **Loc-LLL(\(l\))** is \(O(ndk)\) arithmetic operations.  
Let \(decr\) denote the number of times that the condition  
\[(D(l-1)>(\alpha/\delta)^{k^{2}}D(l)\;\mathrm{or}\;\delta^{k^{2}}\|b^{*}_{k(l-1) }\|^{2}>\alpha\|b^{*}_{k(l-1)+1}\|^{2})\]  
holds and \(l\) is decreased. The number of times **Loc-LLL(\(l\))** is called is \(m-1+2\cdot decr\). [PERSON] and [PERSON] [20] showed that \(decr\leq 2\frac{m-1}{k^{2}}\log_{1/\delta}M_{sc}<2\frac{n}{k^{3}}\log_{1/\delta }M_{sc}\). Hence the total work in the **Segment Size Reduction** step of **Loc-LLL(\(l\))** is \(O(\frac{n^{3}}{k^{2}}\log_{1/\delta}M_{sc})\) arithmetic operations when \(d=O(n)\). This leads to the computational complexity result in Table 1 when \(k=\sqrt{n}\) and \(d=O(n)\). We have omitted details on the bounds on the length of the elements in \(U_{l}\) and \(\Gamma\) (see [PERSON] and [PERSON] [20] for details).