## 3 Storjohann's Improvements
### The Modified LLL Algorithm with Modular Arithmetic  
[PERSON] [14] uses modular arithmetic to keep the intermediate numbers bounded during the algorithm's iterations. Given an integer \(a\), and an integer \(M>0\), we write \(a\pmod{M}\) to mean the unique integer \(r\) congruent to \(a\) modulo \(M\) in the symmetric range, that is, with \(-\lfloor(M-1)/2\rfloor\leq r\leq\lfloor M/2\rfloor\). Similarly, \(U(\text{mod }M)\) stands for the same operation for all entries of matrix \(U\).  
The modular basis reduction algorithm of [PERSON] [14] is given in Figures 8 and 9. Its worst case computational complexity is given in Table 1. The notable difference of this algorithm from the **ModifiedLLL** algorithm is in the modular arithmetic operation that is performed in the methods **ModReduce** and **ModSwap**.  
Let \(M=2\lceil(nM_{0})^{1/2}\rceil+1\) so that by Lemma 1 the entries in the reduced basis matrix upon the termination of the **ModifiedLLL** algorithm are bounded in magnitude by \((M-1)/2\). The modular approach hinges on the observation that \(UB(\text{mod }M)=\bar{U}B(\text{mod }M)\), where \(\bar{U}=U(\text{mod }M)\). Note that in the \"infinite\" precision version of the **ModifiedLLL** algorithm, where the \(\spadesuit\) step is not performed, one allows \(U\) to grow. However, in the modular arithmetic version the elements of \(U\) and \(T\) remain bounded.  
We have shown above how to bound the entries of \(U\) by \(M=O(M_{0})\) during the course of the algorithm. Lemma 1 has already bounded the diagonal entries \(d_{i}\) of \(T\) throughout the algorithm. The following lemma gives a way to keep the off diagonal entries of \(T\) bounded.  
**Lemma 2**: _[_14_]__. Let \(T\) be the matrix of (3.5), \(M\) a positive integer, and \(i\) and \(j\) indices with \(1\leq i<j\leq n\). There exists a unit upper triangular integral matrix \(V\) such that \(TV\) is identical to \(T\) except in the  
Figure 8: The Modular LLL Basis Reduction Algorithm.  
Figure 9: ModSubtract and ModSwap subroutines.  
(i,j)-th entry which is reduced modulo \(d_{i}d_{i-1}M\). Furthermore, \(V\) can be chosen so that \(\bar{V}=V(\mathrm{mod}\ M)\) is the identity matrix._  
[PERSON] [14] constructed the matrix \(V\) in Lemma 2 as follows. Let \(V_{0}\) be the \(n\times n\) strictly upper triangular matrix with column \(j\) equal to column \(i\) of \(F^{t}\) and all other entries zero, let \(q=[T_{i,j}/(d_{i}d_{i-1}M)]\), and take \(V=I-qMV_{0}\). Note that \(V^{t}B\) is also a basis for \(L\). Since the matrix \(V^{t}B\) is not calculated; the corresponding operation should be recorded in \(U\). However, \(U\) remains unchanged, because \(U=\bar{V}^{t}U(\text{mod}\ M)\) and \(\bar{V}=I_{n}\). The entries of matrix \(T\) corresponding to this row transformation on \(B\) are updated by multiplying \(T\) with \(V\), which has the desired effect of reducing \(T_{i,j}\) modulo \(d_{i}d_{i-1}M\). This modular reduction is performed in the **ModReduce** and **ModSwap** calculation. We remark that because of the above operation the intermediate lattice bases \(B\) that correspond to the matrix \(T\) may no longer be polynomially bounded in the size of the starting \(B\), however, it is no longer important because an intermediate \(B\) is never recorded.