## 3 Storjohann's Improvements
### The LLL-Reduction with Fraction Free Computations  
For the matrix \(BB^{t}\) we have an integral lower triangular matrix \(F\) and an integral upper triangular matrix \(T\) such that \(T=F(BB^{t})\) (See [PERSON], [PERSON], and [PERSON] [21]). \(F\) and \(T\) are called the fraction free factors of \(BB^{t}\). Fraction free factors of a matrix are computed in \(O(n^{3})\) arithmetic operations using standard matrix multiplication. It is known that  
\[T=F(BB^{t})= \begin{bmatrix}d_{1}&\ldots&\ldots&\ldots\\ &\ddots&T_{i,j}&\vdots\\ &&\ddots&\vdots\\ &&&d_{n}\end{bmatrix}  \tag{3.5}\]  
where \(T_{i,j}=d_{j}\Gamma_{i,j}\). Recall that \(BB^{t}\) is positive definite since the row vectors of \(B\) are linearly independent. Hence \(T\) and \(F\) are unique. Also, \(F=diag\{1,d_{1},\ldots,d_{n-1}\}\Gamma^{-t}\), \(T=diag\{d_{1},\ldots,d_{n}\}\Gamma\), \(\|b_{i}^{*}\|^{2}=d_{i}/d_{i-1}\) while taking \(d_{0}=1\), and \(d_{1},\ldots,d_{n}\) are integers because \(b_{1},\ldots,b_{n}\) are in \(\mathbb{Z}^{d}\). Note also that \(TF^{t}=diag\{d_{1},d_{1}d_{2},d_{2}d_{3},\ldots,d_{n-1}d_{n}\}\). [PERSON] [14] gave a fast matrix multiplication algorithm for computing \(F\) and \(T\). It requires \(O(n^{\theta}\ln(n)(\ln M_{sc})^{1+\epsilon})\) bit operations on integers of bit length \(O(\ln M_{sc})\), where \(\theta<2.376\) and \(\epsilon\) is a positive constant when the fast matrix multiplication algorithm of [PERSON] and [PERSON] [22] is used. \(\theta=3\) and \(\epsilon=1\) when the standard matrix multiplication is used. In Figure 5 we give [PERSON]'s rearrangement of the computations of Figure 4 using fraction free computation. The **ModifiedLLL** algorithm performs two types of unimodular operations. (i) **FFReduce**: subtracting a multiple of a row of \(B\) from another row of \(B\), and (ii) **FFSwap**: swapping a row of \(B\) with an adjacent row of \(B\). The **ModifiedLLL** algorithm works by recording the unimodular row operations on \(B\) in a unimodular matrix \(U\) initially set to be an identity matrix, and updating the entries of \(T\). There is no need to update \(B\) or \(B^{*}\) in the algorithm, except in a post processing step. It is sufficient to update matrices \(U\) and \(T\) during the algorithm's iterations. The fraction free updates of \(U\) and \(T\) corresponding to these unimodular operations are given in Figures 6 and 7, respectively. Note that one execution of **FFReduce** or **FFSwap** is performed in \(O(n)\) arithmetic operations. **Algorithm: ModifiedLLL**[14]  
INPUT: \(B\in\mathbb{Z}^{n\times d},\delta\);  
OUTPUT: An LLL-reduced basis \(B\);  
(1) [Fraction free Gaussian elimination]  
\(T\gets F(BB^{t})\);  
(2) [\(\delta\)-reduction and size reduction]  
\(k=2\), \(U=I_{n}\);  
WHILE \(k\leq n\) DO  
**FFReduce**(\(U\),\(T\),\(k\),\(k-1\),\([\Gamma_{k-1,k}]\));  
IF \(\frac{d_{k}}{d_{k-1}}<(\delta-\Gamma_{k-1,k}^{2})\frac{d_{k-1}}{d_{k-2}}\) THEN  
_f*_ Case 1. */  
**FFSwap**(\(U,T,k\));  
IF \(k>2\) THEN \(k\gets k-1\);  
ELSE  
_f*_ Case 2. */  
\(\spadesuit\) FOR \(j\) from \(k-2\) to \(1\) DO **FFReduce**(\(U,T,k,j,[\Gamma_{j,k}]\));  
\(k\gets k+1\);  
(3) [Post Processing]  
\(B\gets UB\);  
**Subroutine: FFReduce**(\(U,T,k,r,q\))  
/* Subtract \(q\) times row \(r\) from row \(k\) of \(U\) and update \(T\). */  
\(\mbox{row}(U,k)\leftarrow\mbox{row}(U,k)-q*\mbox{row}(U,r)\);  
\(\mbox{col}(T,k)\leftarrow\mbox{col}(T,k)-q*\mbox{col}(T,r)\);  
**Algorithm:**FFSwap(\(U,T,k\))  
* Switch rows \(k-1\) and \(k\) in \(U\) and update \(T\). */  
switch rows \(k-1\) and \(k\) in \(U\);  
\(\mbox{row}(T,k)\leftarrow(1/T_{k-1,k-1})(T_{k-2,k-2}*\mbox{row}(T,k)+T_{k-1,k }*\mbox{row}(T,k-1))\);  
switch rows \(k-1\) and \(k\) of \(T\);  
switch columns \(k-1\) and \(k\) of \(T\);  
\(\mbox{row}(T,k)\leftarrow(1/T_{k-2,k-2})(T_{k-1,k-1}*\mbox{row}(T,k)-T_{k-1,k }*\mbox{row}(T,k-1))\);  
Figure 5: Modified LLL Basis Reduction Algorithm. Figure 6: Fraction Free Subtract Subroutine. The **LLL** and **ModifiedLLL** algorithms use \(\Delta:=\prod_{i=1}^{n-1}d_{i}\) to measure progress.