MergeLLL: A Hierarchical Divide-and-Conquer Framework for LLL-Based Lattice Reduction Niharika Gauraha1*
arXiv:2606.26784v1 [cs.CR] 25 Jun 2026
1*
Department of Theoretical Computer Science, KTH, The Royal Institute of Technology, Stockholm.
Corresponding author(s). E-mail(s): [email protected]; Abstract Lattice basis reduction algorithms have various applications in computational number theory and lattice-based cryptography, but their complexity increases rapidly with the dimension. Motivated by the divide-and-conquer strategy of merge sort and incorporating PotLLL-style deep insertions during recombination, MergeLLL is proposed. In this framework, a lattice basis is split into sub-bases, local reductions are performed independently, and the full basis is reconstructed through hierarchical merging. The approach is focused on improving local lattice structure first before global basis properties are refined, resulting in enhanced Gram–Schmidt orthogonality and numerical stability, while overall computational cost is reduced. The method is naturally parallelizable, allowing efficient multicore and distributed execution. It is shown that the reduction and merging steps preserve the lattice structure through unimodular transformations and achieve logarithmic parallel depth. In experiments on subset-sum and NTRU-derived lattices, improvements over classical lattice reduction algorithms are demonstrated, including better orthogonality, a reduced number of expensive swap operations, and an improved Hermite factor, indicating higher-quality reduced bases. Keywords: Lattice Reduction, LLL, potLLL, BKZ
1 Introduction Lattice basis reduction is a fundamental tool in several fields, including number theory and modern cryptography. Given a lattice basis, reduction algorithms compute an alternative basis with shorter and more nearly orthogonal vectors while preserving
1
the underlying lattice structure. Since the introduction of the Lenstra–Lenstra–Lovász (LLL) algorithm [1], lattice reduction has become a central component of cryptanalysis, integer programming, Diophantine approximation, and, more recently, the analysis and implementation of post-quantum cryptographic systems [2, 3]. This growing range of applications has also motivated the development of more efficient and scalable reduction algorithms tailored to high-dimensional settings. Among existing reduction techniques, block Korkine–Zolotarev (BKZ) [4, 5] reduction improves over LLL by operating on blocks of the basis, while PotLLL[6] enhances LLL through deep insertions guided by potential minimization, enabling higher-quality reductions in practice. Most lattice reduction algorithms operate globally on the full basis, capturing dependencies among all vectors but at high computational cost. In high dimensions, orthogonalization remains relatively efficient, but swap operations between basis vectors become the main bottleneck, as each swap can trigger a cascade of updates across the basis. These dependencies limit available parallelism, since swaps tend to enforce sequential execution and restrict concurrent updates. To reduce the computational overhead associated with maintaining Gram–Schmidt orthogonalization (GSO) data during lattice reduction, several authors have proposed segment- and block-based approaches[7, 8] . In Segment LLL, the basis is partitioned into overlapping segments that are reduced largely independently before being reconciled recursively. While modern lattice reduction libraries[3] often employ incremental and lazy-update strategies rather than explicit Segment LLL, the underlying principle remains the same: restricting orthogonalization work to local blocks can significantly improve practical performance without substantially affecting reduction quality. In this work, MergeLLL is introduced as a hierarchical divide-and-conquer framework for lattice basis reduction. Inspired by the decomposition and recombination structure of merge sort, the full basis is not treated as a single object. Instead, it is partitioned into smaller sub-bases, independent local reductions are applied, and the resulting components are merged through a hierarchical reduction tree. The central idea behind MergeLLL is that local lattice structure can often be improved before global interactions are considered. Local reductions shorten vectors, improve orthogonality, and reduce conditioning issues within lower-dimensional subspaces. By performing these operations independently, much of the computation can be parallelized. Global structure is then reintroduced through a sequence of merge operations, allowing information to propagate across partitions while preserving the gains from local reduction. A key contribution of this work is a novel hierarchical merging procedure for lattice bases. While the overall framework follows the divide-and-conquer structure of merge sort, the merge step itself constitutes the main algorithmic innovation. Inspired by PotLLL reduction [6], the proposed merge strategy goes beyond simply concatenating independently reduced sub-bases. Instead, it performs structured insertion and reordering operations that progressively restore interactions between partitions and improve basis quality at each level of the hierarchy. From a theoretical perspective, MergeLLL preserves the underlying lattice throughout the reduction process. Each local reduction and merge step consists of unimodular
2
basis transformations, ensuring that every intermediate and final basis generates the same lattice as the original input. Moreover, the hierarchical reduction tree exposes substantial parallelism: for a balanced decomposition, the merge hierarchy has logarithmic depth, while most reduction work is performed independently on disjoint sub-bases. To evaluate the effectiveness of the proposed framework, both classical and cryptographically relevant lattice families are considered. In particular, lattices arising from subset-sum instances [4] and structured lattices derived from NTRU-style constructions [9] are studied. These classes are characterized by distinct reduction challenges and provide insight into the behavior of the hierarchical method on both unstructured and highly structured lattices. The resulting bases are assessed using swap counts, the Hermite factor (HF), and orthogonality error. The results show that basis quality is improved by MergeLLL, while swap counts are reduced, and scalable parallel execution in high-dimensional settings is naturally enabled by its divide-and-conquer structure. The main contributions of this paper are summarized as follows:
• MergeLLL is introduced as a divide-and-conquer framework for lattice basis reduction inspired by the merge-sort paradigm, and a novel hierarchical merging algorithm inspired by PotLLL reduction is proposed, in which interactions between independently reduced sub-bases are progressively restored. • Theoretical properties of the framework are established, including lattice preservation under unimodular transformations and logarithmic parallel depth for balanced decompositions. • The proposed approach is experimentally evaluated on subset-sum and NTRU-style lattices, demonstrating improved orthogonality and reduced swap counts. • It is shown that the hierarchical approach provides an effective and scalable method for lattice reduction in high-dimensional settings, particularly in parallel computing environments.
2 Preliminaries In this section, the definitions and results from lattice theory and lattice basis reduction that are used throughout the paper are briefly recalled.
2.1 Lattices and Bases Let b1 , b2 , . . . , bn be vectors in Rn . Consider the set of all integer linear combinations of these vectors: ( n ) X L= ai bi ai ∈ Z . i=1
Our goal is to study the structure of L and, in particular, to find vectors in L whose Euclidean length is small.
3
Definition 1 (Lattice) A lattice in Rn is the set of all integer linear combinations of a basis b1 , b2 , . . . , bn of Rn , namely ( n ) X L= ai bi ai ∈ Z . i=1
Equivalently, a lattice is a discrete subgroup of Rn generated by a basis of Rn .
Throughout this discussion, it is assumed for simplicity that b1 , b2 , . . . , bn ∈ Zn are linearly independent. Since n linearly independent vectors in Rn form a basis of Rn , these vectors generate a full-rank lattice L ⊆ Rn . Let L be a lattice with basis b1 , b2 , . . . , bn . Associated with this basis is the basis matrix b1 b2 B = . , .. bn whose rows are the basis vectors of the lattice. Let L ⊂ Rn be a full-rank lattice with basis b1 , . . . , bn , and let B be its basis matrix. If B ′ is another basis of L, then there exists a unimodular matrix U ∈ Zn×n such that
B ′ = U B, where U is unimodular, i.e., U is an integer matrix with det(U ) = ±1. Since | det(U )| = 1, it follows that
| det(B ′ )| = | det(U ) det(B )| = | det(B )|. Hence the quantity | det(B )| is independent of the choice of basis.
2.2 Gram–Schmidt Orthogonalization Given a basis (b1 , . . . , bn ), the Gram–Schmidt process produces an orthogonal family (b∗1 , . . . , b∗n ) defined recursively by
b∗i = bi −
X
µi,j b∗j ,
j<i
where
µi,j =
⟨bi , b∗j ⟩ ∥b∗j ∥2
are the Gram–Schmidt coefficients. The vectors b∗1 , . . . , b∗n are mutually orthogonal.
4
2.3 The LLL Algorithm Let B = (b1 , . . . , bn ) be a lattice basis and let (b∗1 , . . . , b∗n ) denote its Gram–Schmidt orthogonalization. The Lenstra–Lenstra–Lovász (LLL) algorithm produces a reduced basis satisfying size reduction and the Lovász condition. For a parameter δ ∈ (1/4, 1), a basis is LLL-reduced if for all i,
|µi,j | ≤
1 , 2
j < i,
and
δ∥b∗i−1 ∥2 ≤ ∥b∗i ∥2 + µ2i,i−1 ∥b∗i−1 ∥2 . The LLL algorithm is outlined in Algorithm 1; for further details, reference is made to the original LLL paper [1]. Algorithm 1 LLL Basis Reduction Input: basis B = (b1 , . . . , bn ), parameter δ ∈ (1/4, 1] Output: LLL-reduced basis B ∗ 3: Compute Gram–Schmidt orthogonalization bi and coefficients
1:
2:
⟨bi ,b∗ ⟩
µi,j ← ⟨b∗ ,bj∗ ⟩ j j 5: k ← 2 6: while k ≤ n do 7: for j = k − 1 downto 1 do 8: if |µk,j | > 12 then 9: r ← round(µk,j ) 10: bk ← bk − rbj 11: Recompute Gram–Schmidt data for affected vectors 12: end if 13: end for 14: if ∥b∗k ∥2 ≥ (δ − µ2k,k−1 )∥b∗k−1 ∥2 then 15: k ←k+1 16: else 17: Swap bk and bk−1 18: Recompute Gram–Schmidt data for affected vectors 19: k ← max(k − 1, 2) 20: end if 21: end while 22: return B 4:
2.4 The PotLLL Algorithm The PotLLL algorithm is a variant of lattice basis reduction based on a global potential function rather than purely local conditions on the Gram–Schmidt coefficients. It was introduced to improve the practical behavior of LLL-type reductions by allowing more flexible swaps while maintaining polynomial-time termination. 5
Let B = (b1 , . . . , bn ) be a lattice basis with Gram–Schmidt vectors (b∗1 , . . . , b∗n ). The potential of B is defined by Pot(B ) =
n Y
∥b∗i ∥2(n−i+1) .
i=1
The central idea of PotLLL is to perform size reduction as in LLL, followed by allowing more general permutations of basis vectors beyond adjacent swaps. A basis transformation is accepted if it strictly decreases the potential. In particular, a basis vector may be moved to an earlier position in the basis if this operation reduces Pot(B ). Thus, PotLLL alternates between:
• Size reduction: ensuring |µi,j | ≤ 1/2 for j < i, as in LLL; • Potential-reducing insertion steps: moving basis vectors to earlier positions whenever this strictly decreases the global potential. Unlike LLL, which enforces only a local Lovász condition between adjacent Gram– Schmidt lengths, PotLLL uses a global criterion that allows long-distance swaps. This often yields better-reduced bases in practice while retaining a polynomial-time complexity guarantee. Upon termination, the basis is size-reduced and locally optimal with respect to the potential function, meaning no single insertion can further decrease Pot(B ). This typically produces bases of quality comparable to or slightly better than classical LLL, particularly in higher dimensions. Algorithm 2 reproduces the PotLLL2 algorithm as presented in the original paper [6]. Throughout this report, potLLL2 is denoted as potLLL, as only a single version is considered.
3 The MergeLLL Construction MergeLLL is now formalized as a divide-and-conquer framework for lattice basis reduction, defined over a hierarchical decomposition tree inspired by merge sort.
3.1 Recursive Decomposition Without loss of generality, an n × n basis matrix is assumed. Let B ∈ Zn×n be a fullrank lattice basis of a lattice L(B ) ⊂ Zn . MergeLLL recursively partitions B into two sub-bases: B = B (1) ∪ B (2) , where B (1) ∈ Zn1 ×n and B (2) ∈ Zn2 ×n with n1 + n2 = n. This induces a binary decomposition tree T (B ), where each node corresponds to a sub-basis of B and the leaves correspond to sufficiently small sub-bases on which local reduction is applied.
6
Algorithm 2 Potential LLL (PotLLL), detailed version Require: Basis B ∈ Zn×m , δ ∈ (1/4, 1] Ensure: A δ -PotLLL reduced basis 1: δ -LLL reduce B 2: ℓ ← 1 3: while ℓ ≤ n do 4: Size-reduce bℓ by b1 , . . . , bℓ−1 5: Update ∥b∗ℓ ∥2 and µℓ,j for 1 ≤ j < ℓ 6: P ←1 7: Pmin ← 1 8: k←1 9: for j = ℓ − 1 downto 1 do Pℓ−1 ∥b∗ℓ ∥2 + i=j µ2ℓ,i ∥b∗i ∥2 10: P ←P · ∥b∗j ∥2 11: if P < Pmin then 12: k←j 13: Pmin ← P 14: end if 15: end for 16: if δ > Pmin then 17: B ← σk,ℓ B 18: Update ∥b∗k ∥2 and µk,j for 1 ≤ j < k 19: ℓ←k 20: else 21: ℓ←ℓ+1 22: end if 23: end while 24: return B B
B1
B11
B2
B12
B21
B22
Fig. 1: Recursive decomposition: demonstrated only up to layer 2.
7
3.2 Local Reduction At each leaf node and during subsequent merges, a local lattice reduction algorithm can be applied to obtain a reduced sub-basis. For this purpose, potLLL is used.
3.3 Merge operation The merge operation can be viewed as adjacent leaves being merged, as shown in the Figure 2. Note that, all intermediate merges before the final merge, in which the two halves are merged, can be viewed as a preprocessing step to the final merge. B11
B12
B21
B1
B22
B2
preprocessing step
Merge
B
Fig. 2: Merge operation: demonstrated only up to layer 2.
Adjacent sub-bases are always merged using potLLL. Suppose the following two blocks are to be merged
B1 = (b1 , . . . , bn1 ),
B2 = (bn1 +1 , . . . , bn2 ),
where both B1 and B2 are independently potLLL-reduced. Then the only modification needed in the original potLLL algorithm for these two inputs is to start from l = n1 +1, and to apply the algorithm to the concatenated basis
B = B1 ∪ B 2 ,
8
where B is obtained by concatenating B2 after B1 . In addition, the initial preprocessing step of PotLLL using classical LLL reduction is omitted. The merge operation is outline in Algorithm 3. The final merge of the two halves of the original basis should be viewed as the last stage in a hierarchical sequence of reductions, where earlier merging operations produce bases that are independently potLLL-reduced on their respective sub-blocks. Although each block B1 and B2 satisfies the potLLL invariants internally, this does not imply that no further internal modifications will occur during the final merge. In particular, operations triggered near the boundary may propagate through sizereduction and potential-improving swaps, potentially affecting vectors deeper inside each block. However, the hierarchical structure is still useful: the previous merging steps significantly reduce the number of violations and ensure that the final merge begins from a highly structured state. Consequently, while the final merge is not strictly confined to boundary corrections, it typically performs substantially fewer swap operations than running potLLL from scratch. It can be argued that the previous merging steps may, in the worst case, be wasteful, in the sense that their overall effect can be comparable to restarting the reduction from scratch on the full basis. In particular, although locally potLLL-reduced blocks are produced by these intermediate merges, global optimality with respect to the final merged basis is not necessarily preserved, and hence the total work required by the final reduction stage may not be reduced. However, empirically, these steps are observed to improve performance in practice. From a parallelization perspective, the earlier merges can be executed independently on disjoint sub-bases, and the algorithm becomes sequential only at the final merge stage. All previous merging operations can be viewed as preprocessing steps for the final merge.
3.4 Correctness of Merging Operation Let B1 = (b1 , . . . , bn1 ) and B2 = (bn1 +1 , . . . , bn2 ) be two bases that are independently potLLL-reduced, and let B = B1 ∪ B2 denote their concatenation. Since both B1 and B2 are already potLLL-reduced, all local reduction conditions (size-reduction and potential-decrease conditions) are satisfied within each block. By starting potLLL from k = n1 + 1 implies that:
• the internal structure of B1 is not immediately revisited, since all pairs (bi , bi+1 ) for i < n1 already satisfy the potLLL conditions at initialization; • only interactions introduced by the concatenation are directly acted upon at the start, although subsequent deep insertions may still propagate updates into earlier indices. Each swap or size-reduction step performed by potLLL strictly decreases the global potential function, which is bounded from below. Therefore, the algorithm terminates after finitely many steps. Upon termination, all adjacent pairs in B satisfy the potLLL conditions, including those near the boundary. Hence, the output basis is potLLLreduced and spans the same lattice as B1 ∪ B2 , establishing correctness of the merging operation. 9
Algorithm 3 MergeReducedBases (PotLLL Insertion of a Basis B2 into B1 ) Require: PotLLL-reduced basis B1 = (b1 , . . . , bn1 ), and B2 = (bn1 +1 , . . . , bn2 ), parameter δ ∈ (1/4, 1) Ensure: δ -PotLLL reduced basis B 1: Set B ← B1 ||B2 ▷ concatinate B1 and B2 2: l ← n1 + 1 3: n ← n1 + n2 4: while ℓ ≤ n do 5: Size-reduce bℓ by b1 , . . . , bℓ−1 6: Update ∥b∗ℓ ∥2 and µℓ,j for 1 ≤ j < ℓ 7: P ←1 8: Pmin ← 1 9: k←1 10: for j = ℓ − 1 downto 1 do Pℓ−1 ∥b∗ℓ ∥2 + i=j µ2ℓ,i ∥b∗i ∥2 11: P ←P · ∥b∗j ∥2 12: if P < Pmin then 13: k←j 14: Pmin ← P 15: end if 16: end for 17: if δ > Pmin then 18: B ← σk,ℓ B 19: Update ∥b∗k ∥2 and µk,j for 1 ≤ j < k 20: ℓ←k 21: else 22: ℓ←ℓ+1 23: end if 24: end while 25: return B
3.5 Complexity Structure Let T (n) denote the computational cost of MergeLLL on a basis of size n. The algorithm satisfies the recurrence
T (n) = 2T (n/2) + M (n), where M (n) denotes the cost of merging two potLLL-reduced sub-bases of total size n. For a balanced decomposition tree, the recursion depth is O(log n). At each level, the two recursive subproblems are independent and can therefore be executed in parallel. As a result, the parallel span of MergeLLL is bounded by
O(log n),
10
up to the contribution of the merge operations M (n) at each level. M (n) can be viewed as the complexity of potLLL, as derived in the original potLLL paper[6].
3.6 The MergeLLL Algorithm The MergeLLL algorithm is outlined in Algorithm 3. It describes a divide-and-conquer procedure in which the basis is recursively split into smaller blocks, reduced independently, and then iteratively merged. At each merging step, adjacent blocks are combined and lattice reduction is applied to the concatenated basis. This strategy is designed to progressively improve the structure of the basis while controlling computational complexity.
Algorithm 4 MergeLLL (using PotLLL) Require: Basis B = (b1 , . . . , bn ), parameter δ ∈ (1/4, 1) Ensure: δ -PotLLL reduced basis B 1: n ← |B| 2: size ← 1 3: while size < n do 4: for lef t ← 1 to n step 2 · size do 5: mid ← min(lef t + size − 1, n) 6: right ← min(lef t + 2 · size − 1, n) 7: if mid < right then 8: B [lef t . . . right] ← MergeReducedBases(B, lef t, mid, right) 9: end if 10: end for 11: size ← 2 · size 12: end while
4 Experimental Evaluation MergeLLL is evaluated as a framework for lattice basis reduction, with emphasis placed on its effect on basis quality and computational behavior. The experiments are conducted on integer lattices of moderate to high dimensions, including instances derived from subset-sum constructions and NTRU-style structured lattices.
4.1 Experimental Setup MergeLLL is implemented as described in Algorithm 4 and in a parallelized form. Within the same framework, the classical LLL algorithm [1] is also implemented following its original specification. A fair comparison is ensured by using identical numerical precision, Gram–Schmidt orthogonalization, and basis update procedures. All experiments are implemented in C++ and run on the PDC (KTH) highperformance computing cluster. Computations are carried out on the main partition under the project account naiss2026-4-509. Each run uses a single compute node with 64 CPU cores. 11
In all experiments, the reduction parameter is set to δ = 43 . All figures in this paper are generated using the Python Matplotlib library.
4.2 Evaluation Metrics In this work, the Hermite factor (HF) and the orthogonality error are considered as measures for evaluating a lattice basis. These quantities capture both the lengths of the basis vectors and the degree to which the basis approaches orthogonality. They are particularly useful for analyzing the performance of lattice reduction algorithms.
• Orthogonality Error (OE): Let B ∈ Rn×n be a lattice basis whose rows b1 , . . . , bn are the basis vectors. Let the QR decomposition of B T be B T = QR, where Q has orthonormal columns. The orthogonality error is defined as OE(B ) = ∥QT Q − I∥F . This quantity measures the deviation from perfect orthogonality, and smaller values indicate better numerical stability and a more orthogonal structure of the basis. • Hermite’s Factor (HF): The Hermite factor of a basis B is defined as HF(B ) =
∥b1 ∥ det(L)1/n
This quantity is always greater than or equal to 1, and smaller values indicate better reduced bases, with values closer to 1 corresponding to higher-quality reductions. • Swap Count: The number of swap operations performed in the final merge stage of MergeLLL is reported, measuring the global recombination cost. The total swap count is also reported, defined as the sum of all swap operations across all levels of the merge tree. For the classical LLL algorithm, the total number of swaps performed during the reduction process is reported.
4.3 Test Instances Classical LLL and MergeLLL are compared under identical experimental conditions. The evaluation is conducted on two complementary families of lattices with varying dimensions to assess scalability and numerical stability.
• Subset-sum lattices: combinatorial and largely unstructured instances constructed using the standard subset-sum embedding as in the BKZ benchmarking framework[5]. The lattice dimension ranges from 21 to 401 in increments of 20. The subset-sum instances use bit-length parameters 20 and 40, allowing us to probe numerical instability in lattice reduction under increasing hardness. Pn Let a = (a1 , . . . , an ) ∈ Zn and S = i=1 ai xi for xi ∈ {0, 1}. A basis B ∈ Z(n+1)×(n+2) is constructed with rows b1 , . . . , bn+1 . 12
For i = 1, . . . , n,
bi = (0, . . . , 0, 2, 0, . . . , 0, nai , 0), where 2 is in position i. The additional vector is
bn+1 = (1, 1, . . . , 1, nS, 1). The vector bn+1 enforces the subset-sum constraint within the lattice embedding. • NTRU-style lattices: structured lattices arising from ring-based NTRU constructions, exhibiting strong algebraic dependencies induced by convolution structure in polynomial rings. Specifically, the lattice basis has the form
qI 0 , H I
where H is a circulant matrix generated from a random polynomial h. In the experiments, q = 231 − 1 is used. The dimension is varied from 20 to 100 in increments of 20.
4.4 Experiment 1 In this experiment, MergeLLL is evaluated on subset sum lattice bases generated using 20-bit integer weights and compared with the classical LLL algorithm. The instance size is varied from 20 to 400, and runtime, number of swaps, Hermite factor, and orthogonality error are measured. The results are reported in Table 1 and Figure 3. For MergeLLL, the reported swap count corresponds to the final merge step, while the value in parentheses denotes the total number of swaps accumulated across all merge operations in the hierarchical merge tree.
Fig. 3: Runtime comparison for Subset Sum instances with weights of bit-length 20
13
Table 1: Reduction quality metrics for Subset Sum instances with weights of bit-length 20. The value in parentheses in the MergeLLL Swaps column denotes the total number of swaps accumulated across all merge operations in the hierarchical merge tree. LLL
MergeLLL
Dimension
Swaps
HF
OrthErr
Swaps
HF
OrthErr
21 41 61 81 101 121 141 161 181 201 221 241 261 281 301 321 341 361 381 401
444 450 677 830 1159 1064 1186 1460 1046 1455 1103 1106 1519 1501 1234 1470 1325 1312 1327 1468
1.0421 1.8218 2.0990 1.9490 2.0319 1.9086 1.9463 2.3406 2.1949 2.5617 2.2371 2.4315 2.0692 2.7905 2.0888 2.4789 2.1013 2.6694 2.5043 2.3242
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
81 (408) 70 (1142) 605 (2394) 282 (3095) 492 (4201) 614 (5373) 113 (6136) 456 (7185) 765 (8283) 760 (9586) 799 (10620) 1088 (12253) 21 (12923) 332 (13842) 506 (14799) 1258 (16178) 1067 (17324) 1017 (18689) 1144 (19665) 1538 (20356)
1.0421 1.7041 1.6594 1.7791 1.6590 1.7071 1.5076 1.9782 1.7921 2.0252 2.0422 1.5918 2.0692 1.8603 2.0888 1.8739 2.1013 1.8875 1.6394 1.8977
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
4.5 Experiment 2 The experimental setup is identical to that of Experiment 1, except that the subset sum lattice bases are generated using 40-bit integer weights for all instances. The results are reported in Table 2 and Figure 4. The experiments are stopped at dimension 181, as the extremely small Hermite factors observed for the classical LLL algorithm appear suspicious and potentially indicative of numerical instability or inconsistencies in the computation at larger dimensions. In contrast, MergeLLL remains stable and feasible across all tested instances.
14
Fig. 4: Runtime comparison for Subset Sum instances with weights of bit-length 40
Table 2: Reduction quality metrics for Subset Sum instances with weights of bitlength 40. The value in parentheses in the MergeLLL Swaps column denotes the total number of swaps accumulated across all merge operations in the hierarchical merge tree. LLL
MergeLLL
Dimension
Swaps
HF
OE
Swaps
HF
OE
21 41 61 81 101 121 141 161 181
462 3006 8932 13029 38036 49511 176879 71786 97651
2.00085 × 10−13 1.38483 × 10−14 4.80117 × 10−15 1.23319 × 10−15 9.57758 × 10−16 1.25102 × 10−15 2.31473 × 10−16 2.02502 × 10−16 1.93487 × 10−16
14.0680 22.9170 29.0202 36.6182 35.8860 71.5807 69.4107 89.2411 146.6390
120 (766) 306 (2822) 1403 (5306) 300 (7125) 1425 (10233) 1812 (12273) 192 (14959) 1082 (17997) 1773 (20254)
1.24350 1.77711 2.11816 2.37521 2.46826 2.22639 2.79528 2.87830 2.94673
14.0680 22.9170 29.0202 36.6182 35.8860 94.2789 114.0370 98.9547 144.4760
4.6 Experiment 3 The experimental setup is identical to that of Experiment 1, except that NTRU-style lattice bases were used instead of subset sum bases. The lattice dimension was varied from 20 to 100. Higher dimensions were not explored because the runtime of the classical LLL algorithm increased significantly, making the computations prohibitively slow. The results are reported in Table 3 and Figure 5.
15
Table 3: Reduction quality metrics for NTRU-style bases. The value in parentheses in the MergeLLL Swaps column denotes the total number of swaps accumulated across all merge operations in the hierarchical merge tree. LLL Dimension 20 40 60 80 100
Swaps 27772 129312 286699 407858 397641
HF 1.92468 4.01290 10.9077 2.57751 0.0414595
MergeLLL OE −13
1.03084 × 10 6.83773 × 10−10 9.04537 × 10−8 148.497 155.502
Swaps
HF
OE
6097 (12532) 32636 (75172) 181995 (190936) 138647 (338918) 272606 (413119)
0.990288 2.80627 6.08627 11.0507 0.341608
4.70932 × 10−14 3.09012 × 10−11 4.93800 × 10−8 1.07311 × 10−5 178.499
Fig. 5: Runtime comparison for NTRU-style lattice instances
4.7 Discussion The experimental results support the main design principle of MergeLLL: lattice reduction can be effectively decomposed into local reduction followed by controlled global recombination. By isolating most of the reduction effort into independent sub-bases, the framework enables substantial parallelism while maintaining strong overall basis quality. Across both Subset Sum and NTRU-style lattice experiments, the proposed MergeLLL method consistently outperforms classical LLL in runtime while maintaining comparable or better numerical behavior. For Subset Sum instances (20-bit bases, dimensions up to 400), MergeLLL achieves substantial speedups, with runtime growing moderately compared to the rapidly increasing cost of classical LLL. In many mid-to-large dimensions, LLL becomes several times to orders of magnitude slower, while MergeLLL remains practically feasible. The reduction quality (Hermite factor and orthogonality error) is broadly comparable
16
between the two methods, indicating that the speedup does not come at a significant loss of lattice reduction quality. For NTRU-style bases, the gap is even more pronounced. Classical LLL becomes prohibitively expensive beyond moderate dimensions, reaching runtimes in the thousands to tens of thousands of seconds, whereas MergeLLL remains significantly faster across all tested cases. Although both methods show variability in Hermite factors and orthogonality error, MergeLLL maintains stable behavior and produces competitive reduced bases. Overall, the results demonstrate that MergeLLL provides a scalable alternative to classical LLL, especially for structured lattice families such as Subset Sum and NTRUstyle, where standard LLL becomes computationally impractical at higher dimensions.
5 Conclusion and Future Work In this work, the MergeLLL framework for lattice basis reduction is proposed and evaluated, and it is compared against the classical LLL algorithm on Subset Sum and NTRU-style lattice instances. Across all experiments, MergeLLL is observed to consistently demonstrate significantly improved scalability, achieving substantial runtime reductions, particularly at higher dimensions where classical LLL becomes computationally expensive. Despite the reduction in runtime, the quality of the reduced bases is observed to remain comparable, as indicated by similar Hermite factors and orthogonality errors. This suggests that the proposed hierarchical merge strategy provides an effective tradeoff between efficiency and reduction quality. Overall, the experimental results indicate that MergeLLL is a practical and scalable alternative to classical LLL for structured lattice families, especially in regimes where standard LLL becomes infeasible due to computational cost.
5.1 Future Work The current implementation is written in C++, where basis matrix entries are stored as long long, while Gram–Schmidt orthogonalization and the corresponding coefficients are computed in double precision. Future directions include:
• Extending the implementation to use arbitrary-precision arithmetic via MPFR (Multiple Precision Floating-Point Reliable) library[10] to improve numerical stability for large instances. • Evaluating the algorithm on SVP Challenge lattice bases[11] to test performance on standard benchmark instances. • Comparing the proposed method against state-of-the-art libraries such as fplll[12]. • Developing an alternative implementation based on the ”Deep insertion”[8] strategy. • Incorporating BKZ reduction at the leaf nodes with varying block sizes to study quality–performance trade-offs.
17
6 Supplementary information Not Applicable.
7 Acknowledgements The support of the PDC Center for High Performance Computing at KTH Royal Institute of Technology is gratefully acknowledged. The computational resources used in this work were provided under the project naiss2026-4-509.
Declarations Not Applicable.
References [1] Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261(4), 515–534 (1982) [2] Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: A Cryptographic Perspective. Springer, Boston, MA (2002) [3] Nguyen, P.Q., Vallée, B. (eds.): The LLL Algorithm: Survey and Applications. Springer, Berlin, Heidelberg (2010) [4] Schnorr, C.-P., Euchner, M.: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical Programming 66, 181–199 (1994) [5] Chen, Y., Nguyen, P.Q.: Bkz 2.0: Better lattice security estimates (2011) [6] Fontein, F., Schneider, M., Wagner, U.: Potlll: A polynomial time version of lll with deep insertions. Designs, Codes and Cryptography 73, 355–368 (2014) [7] Schnorr, C.P.: Fast lll-type lattice reduction. Information and Computation 204(1), 1–25 (2006) [8] Schnorr, C.-P.: Block reduced lattice bases and successive minima. In: STACS, pp. 57–66 (1994) [9] Hoffstein, J., Pipher, J., Silverman, J.H.: Ntru: A ring-based public key cryptosystem. In: ANTS III, pp. 267–288 (1998) [10] Fousse, L., Hanrot, G., Lefèvre, V., Pélissier, P., Zimmermann, P.: MPFR: A multiple-precision binary floating-point library with correct rounding. ACM Transactions on Mathematical Software 33(2), 13 (2007) https://doi.org/10. 1145/1236463.1236468
18
[11] Nguyen, N.: SVP Challenge: Sample lattices for testing SVP algorithms. https: //www.latticechallenge.org/svp-challenge/ (2026) [12] team, T.f.: fplll, a lattice reduction library. https://github.com/fplll/fplll (2024)
19