# Optimizing Lattice Basis Reduction Algorithm on ARM V8 Processors
## 2 Technical Background
### Lll_FP Algorithm  
NTL (Number Theory Library) is a C++ number theory library for efficiently working with integers and finite fields. The NTL library when it comes to the LLL algorithm has different types of variants like FP(double), QP(quad_float), XD(xdouble), and an RR type. These are all variants of the original LLL algorithm. FP stands for double precision. This paper chooses to optimize the LLL_FP algorithm, which can be used in conjunction with optimization methods such as SIMD vectorisation to speed up the algorithm with a small loss in accuracy. The computational kernel of the LLL_FP algorithm consists of depth insertion, row transformation, and Gram-Schmidt coefficient computation. The Gram-Schmidt computation consists of Kahan summation [24] and inner product computation. The Deep Insertion strategy improves the selection of row swaps in the LLL_FP algorithm. The algorithm not only checks whether the length ratio of the current row to the immediately preceding row vector satisfies the required orthogonality or normalization conditions, but also advances several rows to find the optimal insertion point for better control of the length ratio. The LLL_FP algorithm reduces the basis vectors by progressively making the matrix satisfy the LLL condition through matrix row transformations. Each iteration of the algorithm determines the need for row transformations based on the value of the Gram-Schmidt coefficient. If the coefficient exceeds a threshold, the relevant rows are adjusted to bring the matrix closer to the ideal state. The row transformation is both the core operation of adjusting the matrix and the basis for determining row swaps or insertions. The Kahan Summation algorithm is an algorithm used to reduce the rounding error in summation operations. It is mainly used for summing a series of floating-point numbers to prevent the accumulation of errors caused by the limitations of floating point precision in the summation operation. In standard floating point summations, accumulated rounding errors can result in a loss of precision. Kahan summation reduces the effect of cumulative error by using an additional variable, called a compensator, to track the partial error, and incorporate it into the next addition operation. During each addition operation, the current value is added to the compensator, and the result is stored as a new compensator. Then, the compensator is added to the next value, and the compensator is updated. Finally, all the values are summed, and the final compensator is added to obtain the final summation result. The Kahan algorithm effectively reduces the error of the sum result caused by rounding errors by mitigating the sum error in each iteration. This makes the algorithm more accurate for calculating the sum of floating point numbers, especially when the number of accumulation operations is large or the precision of floating point numbers is low. The Gram-Schmidt coefficient calculation is the core step of the Gram-Schmidt orthogonalisation (Algorithm 1), based on the Schmidt orthogonalisation formula and combined with Kahan summation to achieve error compensation. Its main function is to compute the orthogonal vectors for the k row of the input matrix B with guaranteed accuracy. Specifically, it calculates the inner product of the k row and the previous k-1 row, determines whether high accuracy is required based on the value of the inner product and the length of the vectors, accumulates the error to correct the inner product, generates the Gram-Schmidt coefficients, and updates the buffer to obtain the length of the kth row after orthogonalisation. By calculating the inner product and correcting the error, the procedure ensures that the generated set of orthogonal vectors satisfies orthogonality and length normality, thus realising the orthogonal basis transform of the vector space.