Explicit cost analysis of Toom-4 multiplication for incomplete NTT in lattice-based cryptography
arXiv:2605.17505v1 [cs.CR] 17 May 2026
Sakura Oku and Momonari Kudo Department of Information and Communication Engineering Fukuoka Institute of Technology 3-30-1 Wajiro-higashi, Higashi-ku, Fukuoka 811-0295, Japan [email protected], [email protected] May 19, 2026
Abstract Polynomial multiplication is fundamental in lattice-based cryptography. While the Number Theoretic Transform (NTT) enables fast multiplication, it imposes constraints on the modulus of the coefficient field. Hafiz et al. (2025) addressed this limitation by analyzing the incomplete NTT, which combines a truncated NTT with conventional multiplication methods. In this work, we revisit Toom-4 multiplication in the context of incomplete NTT. Although Toom-4 is asymptotically faster than Karatsuba, its precise cost has not been expressed in a form compatible with the incomplete NTT framework. We present a concrete Toom-4 implementation and derive explicit operation counts that separate additions/subtractions and multiplications over the coefficient field. Our analysis based on addition chains yields a simple cost model for incomplete NTT. Using this model, we analyze hybrid strategies combining Toom-4, Karatsuba, and incomplete NTT. We identify parameter ranges where Toom-4 is advantageous and validate the predicted behavior experimentally.
1
Introduction
In practical lattice-based cryptosystems such as Kyber (ML-KEM) [6, 1] and Dilithium (MLDSA) [9, 2], computations are performed over residue rings of the form Rq = Fq [x]/hxn +1i, where q is an odd prime and n is a 2-power. The full, or complete, Number Theoretic Transform (NTT) provides fast polynomial multiplication in this setting, but requires the condition 2n | (q − 1). This restriction can limit the choice of parameters and affect other design goals such as security and efficiency. To address this issue, Hafiz et al. [10] formulated and analyzed the incomplete NTT, which relaxes this constraint by combining a truncated NTT with conventional polynomial multiplication methods. Their work provides a cost model showing that such hybrid strategies can improve performance when the full, or complete, NTT is not available. In this context, it is natural to consider fast multiplication algorithms such as Karatsuba [11] and Toom–Cook [14, 7] within their incomplete NTT framework. 1
While the complexity of Karatsuba is well understood, the precise cost of Toom-4 – especially its constant factors – has not been expressed in a form compatible with the cost model of incomplete NTT. Although prior work, such as Bodrato and Zanoni [5], studied optimized evaluation and interpolation schemes for Toom–Cook multiplication, these analyses are not directly suitable for integration into the incomplete NTT framework of Hafiz et al. [10]. The main contribution of this paper is to bridge this gap. We present a concrete Toom-4 implementation and derive explicit operation counts separately tracking additions/subtractions and multiplications in the coefficient field. Our analysis is based on addition-chain constructions, which enable a systematic determination of constant factors. The resulting cost model can be directly integrated into the operation-count framework of incomplete NTT. Our contribution is not a new multiplication algorithm, but a precise constant-level analysis of Toom-4 multiplication tailored to the incomplete NTT framework. To the best of our knowledge, such an explicit Toom-4 cost model has not been previously integrated into the incomplete NTT framework. Using this refined model, we analyze hybrid multiplication strategies combining Toom-4, Karatsuba, and incomplete NTT. This allows us to identify parameter ranges where Toom-4 becomes advantageous and to determine the optimal recursion depth. We also provide a Python implementation, together with verification scripts for the addition-chain counts, and experimentally confirm the predicted behavior for NTT-unfriendly prime moduli near the Dilithium modulus. The Toom-4/Karatsuba hybrid is most effective when the admissible NTT depth is small. The implementation and the scripts for verifying the addition-chain optimality are available at [13].
2
Preliminaries
This section reviews incomplete NTT and Toom–Cook multiplication used throughout the paper.
2.1
Notation
Let K be a field, and K[x] the univariate polynomial ring over K. For φ(x) ∈ K[x], we write hφ(x)i for the principal ideal generated by φ(x). For f (x) ∈ K[x] and nonzero φ(x) ∈ K[x], the remainder of f (x) modulo φ(x) is denoted by f (x) mod φ(x). We identify an element of K[x]/hφ(x)i with its canonical representative of degree less than deg(φ). For a prime power q, we denote by Fq the finite field of order q. When q is fixed, let A and M denote one addition/subtraction and one multiplication in Fq , respectively. In lattice-based cryptography, one often works over residue rings of the form Fq [x]/hφ(x)i. A typical choice is the 2n-th cyclotomic polynomial φ(x) = xn + 1 with n a 2-power, since such rings admit efficient arithmetic and fast polynomial multiplication. This setting is used in RingLWE and Module-LWE based cryptosystems such as Kyber (ML-KEM) [6, 1] and Dilithium (ML-DSA) [9, 2]. Hence, fast multiplication in Rq = Fq [x]/hxn + 1i is of central practical importance.
2.2
Incomplete Number Theoretic Transform
The Number Theoretic Transform (NTT) is a finite-field analogue of the Fast Fourier Transform (FFT) [8, 3]; see also [12]. It is used to realize fast polynomial multiplication over residue rings, with O(n log2 n) arithmetic operations over Fq for input degree less than n. Let q be an odd 2
prime, let n = 2k , and put Rq = Fq [x]/hxn + 1i. The full, or complete, NTT over Rq requires a primitive 2n-th root of unity in Fq , equivalently 2n | (q − 1). The incomplete NTT [10] relaxes this condition by using only depth ℓ, where 0 ≤ ℓ ≤ k and 2ℓ+1 | (q − 1), and then combining the transform with another conventional polynomial multiplication method. The case ℓ = k gives the full NTT, while ℓ = 0 gives no transform. Moreover, incomplete NTT can be implemented non-recursively and in-place on the coefficient representation of Rq , see, e.g., [1, 10]. Assume that 2ℓ+1 | (q − 1). We choose and fix a primitive 2ℓ+1 -th root of unity ζ2ℓ+1 in ℓ ℓ+1 -th roots of unity, and we have Fq . Then ζ22j+1 ℓ+1 (0 ≤ j ≤ 2 − 1) are exactly the primitive 2 Q ℓ −1 n/2ℓ . By the Chinese Remainder Theorem (CRT), we also obtain − ζ22j+1 x xn + 1 = 2j=0 ℓ+1 the ring isomorphism Rq = Fq [x]/hx + 1i ∼ = n
ℓ −1 2M
ℓ
Fq [x]/hxn/2 − ζ22j+1 ℓ+1 i,
j=0
where the ring isomorphism is explicitly given by ℓ
ℓ
2 −1 NTT(ℓ,k) : f 7→ (f mod xn/2 − ζ22j+1 ℓ+1 )j=0 ,
where we identify an element of Rq with its canonical representative of degree less than n. Then, the procedures of incomplete NTT are summarized as follows: Outline of Incomplete NTT: Given f, g ∈ Rq and an integer ℓ with 0 ≤ ℓ ≤ k, the following procedures compute f g ∈ Rq : 1. Compute f := NTT(ℓ,k) (f ) and g := NTT(ℓ,k) (g), each entry of which is a polynomial of degree less than n/2ℓ . 2. Compute the product h := f ∗ g in the codomain of NTT(ℓ,k) by entry-wise polynomial multiplications with another multiplication method. 3. Compute NTT−1 (ℓ,k) (h), and output it. The maps NTT(ℓ,k) and NTT−1 (ℓ,k) are computed using the same radix-2 butterfly operations as in standard NTT implementations; see, e.g., [1, 10]. Each level processes n coefficients using n/2 multiplications by twiddle factors and n additions/subtractions, yielding a cost of (ℓn/2)(2A+M) for each transform. In the inverse transform, the divisions by 2 can be postponed and combined into a single multiplication by 2−ℓ ∈ Fq . This results in an additional (n 1ℓ>0 )M, where 1ℓ>0 = 1 if ℓ > 0 and 0 otherwise. Hence we have the following theorem: Theorem 2.2.1 (cf. [10], Observations 3 & 4). Let C(n; ℓ) denote the operation cost of multiplyℓ ing two elements in one CRT component Fq [x]/hxn/2 − ζ22j+1 ℓ+1 i, which is independent of j in the −ℓ operation-count model used here. Suppose that 2 ∈ Fq and the powers of ζ2ℓ+1 are computed in advance. Then, the total operation cost of incomplete NTT is 3(ℓn/2)(2A + M) + 2ℓ C(n; ℓ) + (n 1ℓ>0 )M.
(2.1)
In practice, incomplete NTT is used with an intermediate depth ℓ and combined with another multiplication method such as Karatsuba [11] or Toom–Cook [14, 7] for the smaller subproblems. For example, Kyber (ML-KEM) [6, 1] uses (n, q) = (256, 3329) with depth ℓ = 7, whereas Dilithium (ML-DSA) [9, 2] uses (n, q) = (256, 8380417) with depth ℓ = 8 supporting the full NTT. 3
2.3
Toom–Cook polynomial multiplication
We describe Toom–Cook polynomial multiplication [14, 7] with a splitting parameter s (Toom-s method). Let s, d > 1, let {α0 , α1 , . . . , α2s−2 } be a set of 2s − 1 distinct points in K ∪ {∞}, and let f, g ∈ K[x] be polynomials of degree less than d. If necessary, replace d by the smallest integer d′ ≥ d such that s | d′ , and still denote d′ by d. Ps−1 Ps−1 Splitting: Write f = i=0 fi xid/s P and g = i=0 gi xid/s withP fi , gi ∈ K[x] and deg(fi ), deg(gi ) < s−1 s−1 i i d/s, and write them as F (X) = f X and G(X) = i=0 i i=0 gi X in K[x][X] by putting X = xd/s . Evaluation: For each 0 ≤ i ≤ 2s − 2, compute F (αi ) and G(αi ), which are polynomials in x of degree less than d/s. Recursive multiplication: Compute recursively the products Mi = F (αi )G(αi ) ∈ K[x] for 0 ≤ i ≤ 2s − 2. Interpolation: Recover H(X) ∈ K[x][X] of degree at most 2s − 2 such that H(αi ) = Mi for 0 ≤ i ≤ 2s − 2. Re-composition: We obtain f (x)g(x) = H(xd/s ). The case s = 2 yields Karatsuba multiplication [11]. When working over Fq [x]/hxd − ωi with ω ∈ Fq r {0}, one finally reduces modulo xd − ω. This reduction costs (d − 1)(A + M), which is reduced to (d − 1)A if ω = ±1. It is well-known that the asymptotic complexity of Toom-s is O(dlogs (2s−1) ). Since our target applications involve residue rings defined by 2-power cyclotomic polynomials and their hybridization with NTT, the degrees d of the resulting subproblems are also powers of 2. Therefore, Toom-4 is more compatible with recursive splitting than Toom-3, since the latter requires padding at multiple recursion levels in power-of-two settings. In this paper, we focus on precise cost estimates including constant factors, especially for the case s = 4 (Toom-4) and its hybridizations.
3
Main results
In this section, we first derive explicit operation counts, including constant factors, for our concrete Toom-4 implementation. We then analyze its hybridization with Karatsuba multiplication and incomplete NTT over the residue ring Rq .
3.1
Explicit Toom-4 cost model for incomplete NTT
Here, we present a concrete Toom-4 implementation together with an explicit complexity analysis including constant factors. For finite-field polynomial multiplication inside CRT components of incomplete NTT, we require operation counts compatible with the cost model of [10]. The choice of evaluation points and the evaluation/interpolation schedules significantly affects the constant factors of Toom–Cook multiplication; see, e.g., [5]. Our purpose here is not to optimize Toom–Cook implementations in full generality, but to obtain a field-operation count suitable for hybridization with incomplete NTT. For this reason, we adopt integer evaluation points, avoid fractional constants, and implement the scalar multiplications in interpolation via addition chains, postponing all divisions to a final scaling step, thereby yielding a simple and explicit operation count.
4
Assume that the characteristic of K is neither 2, 3, nor 5. We use the seven evaluation points {0, ±1, ±2, 3, ∞}. We also assume that the input size d is divisible by 4; otherwise, zero-padding is applied as described in Section 2.3. Splitting: We split the input polynomials f (x) and g(x) in K[x] of degree less than d as described in Section 2.3, say f (x) = f0 (x) + f1 (x)xd/4 + f2 (x)x2d/4 + f3 (x)x3d/4 , g(x) = g0 (x) + g1 (x)xd/4 + g2 (x)x2d/4 + g3 (x)x3d/4 , where fi and gi are polynomials of degree less than d/4. Put F (X) := f0 + f1 X + f2 X 2 + f3 X 3 ,
G(X) := g0 + g1 X + g2 X 2 + g3 X 3 .
Evaluation: We compute F (0) = f0 ,
F (∞) = f3 ,
F (3) = f0 + 3f1 + 9f2 + 27f3
F (±1) = f0 ± f1 + f2 ± f3 ,
F (±2) = f0 ± 2f1 + 4f2 ± 8f3
and similarly for G(0), G(±1), G(±2), G(3), G(∞), where F (∞) and G(∞) denote the leading coefficients of F (X) and G(X), respectively, as polynomials in X. The values F (±1), F (±2), and F (3) can be computed as follows: 1. a1 := f0 + f2 ; a2 := f1 + f3 ; a3,± := a1 ± a2 (= F (±1)); 2. a4 := f3 + f3 (= 2f3 ); a5 := a4 + f3 (= 3f3 ); 3. a6,± := a3,± ± a5 (= f0 ± f1 + f2 ± 4f3 ); 4. a7,± := a6,± + f2 (= f0 ± f1 + 2f2 ± 4f3 ); 5. a8,± := 2a7,± (= 2f0 ± 2f1 + 4f2 ± 8f3 ); 6. a9,± := a8,± − f0 (= F (±2)); 7. a10 := 2a5 (= 6f3 ); 8. a11 := a9,+ − f0 + a10 (= 2f1 + 4f2 + 14f3 ); 9. a12 := 2a11 (= 4f1 + 8f2 + 28f3 ); 10. a13 := a12 + a3,− (= F (3)). Applying the same procedure to G, the evaluation step requires 19×2 = 38 additions/subtractions of polynomials of degree less than d/4, that is, 38(d/4) additions/subtractions in K. Recursive multiplication: Compute Mα := F (α)G(α) for α ∈ {0, ±1, ±2, 3, ∞}, where H(X) := F (X)G(X) ∈ K[x][X]. P Interpolation: Writing H(X) = 6i=0 hi X i for hi ∈ K[x] with deg(hi ) < 2d/4, the conditions H(α) = Mα for α ∈ {0, ±1, ±2, 3} together with H(∞) = h6 = M∞ yield a linear system in h0 , . . . , h6 . Its coefficient matrix is a slightly modified Vandermonde matrix, whose rows
5
correspond to the evaluations at α = 0, 1, −1, 2, −2, 3, ∞ in this order. The inverse matrix of the coefficient matrix is 120 0 0 0 0 0 0 −40 120 −60 −30 6 4 −1440 −150 80 80 −5 −5 0 480 1 50 −70 −5 35 −5 −5 1800 120 −20 −20 5 5 0 −600 30 −10 10 5 −5 −1 1 −360 0
0
0
0
0
0
120
Using this inverse matrix, each hi can be expressed as a linear combination of the values Mα = H(α). For example, h1 = 120−1 − 40H(0) + 120H(1) − 60H(−1) − 30H(2) + 6H(−2) + 4H(3) − 1440H(∞) , and h2 , . . . , h5 are obtained similarly. Hence the nontrivial interpolation coefficients have denominator 120, so we work with the scaled quantities h′i := 120hi throughout the recursion. Thus, after L recursive Toom-4 levels, the output is scaled by 120L and recovered by a single final multiplication by the precomputed inverse 120−L ∈ K. The recursion is terminated at a suitable base case, where Karatsuba or schoolbook multiplication is used. For this interpolation step, we first compute several scalar multiples of each H(α) appearing in the above inverse matrix. Thus, rather than generating a single scalar multiple, we consider addition chains for a prescribed set of target multiples. For a finite set S of positive integers, an addition chain for S is a sequence 1 = b0 , b1 , . . . , br such that each bm with 1 ≤ m ≤ r is of the form bi + bj for some 0 ≤ i, j < m, and S ⊂ {b0 , . . . , br }. Using such an addition chain, the required scalar multiples can be computed with r additions. The following chains minimize the number of additions needed to generate all required scalar multiples within the prescribed target sets. The optimality of these chains for the prescribed target sets was verified by exhaustive enumeration up to the relevant lengths, together with elementary lower-bound arguments for the remaining large targets. The verification scripts are included in our public repository [13]. H(0) : 1, 2, 4, 8, 10, 20, 30, 40, 50, 100, 120, 150; H(1) : 1, 2, 4, 8, 10, 20, 30, 40, 70, 80, 120; H(−1) : 1, 2, 4, 5, 10, 20, 40, 60, 80; H(2) : 1, 2, 4, 5, 10, 20, 30, 35; H(−2) : 1, 2, 4, 5, 6; H(3) : 1, 2, 4, 5; H(∞) : 1, 2, 4, 8, 10, 20, 40, 80, 120, 240, 360, 480, 600, 1080, 1440, 1800. The boldface entries indicate the scalar multiples appearing in the above inverse matrix. Thus, all required scalar multiples are obtained with 11 + 10 + 8 + 7 + 4 + 3 + 15 = 58 additions of polynomials of degree less than 2d/4, namely 58(2d/4) additions in K. This explicit control of scalar multiplications is crucial in the incomplete NTT setting, where constant factors directly affect the optimal hybrid strategy. 6
Once these scalar multiples are prepared, the scaled coefficients h′i are recovered by additions/subtractions. For instance, the scaled coefficient h′1 is obtained with 6 additions/subtractions once the relevant scalar multiples have been computed. Similarly, h′2 , h′3 , h′4 , and h′5 are obtained with 5, 6, 5, and 6 additions/subtractions, respectively. Hence the polynomials h′1 , . . . , h′5 are recovered with 28 additions/subtractions of polynomials of degree less than 2d/4, that is, 28(2d/4) additions/subtractions in K. Re-composition: At the scaled level, recovering 120H(xd/4 ) from h′0 , . . . , h′6 requires 6 additions on overlapping blocks of size d/4, namely 6(d/4) additions in K. Indeed, since each h′i has degree less than 2d/4, the supports of h′0 , h′1 xd/4 , . . . , h′6 x6d/4 overlap only with adjacent blocks. Hence the recomposition can be carried out with 6 additions on overlapping blocks of size d/4. Collecting the above counts, one Toom-4 level requires 38(d/4) + (58 + 28)(2d/4) + 6(d/4) = 54d additions in K, where the three terms correspond to evaluation, interpolation, and recomposition, respectively. The final rescaling by the precomputed inverse of the accumulated factor to the output polynomial requires 2d − 1 further multiplications in K. Proposition 1. Let TA (d) and TM (d) denote the numbers of additions/subtractions and multiplications in K required by the recursive part of the proposed Toom-4 implementation on inputs of size d, excluding the final rescaling. Then we have TA (d) = 7 TA (d/4) + 54d and TM (d) = 7 TM (d/4). In addition, the final rescaling step requires 2d − 1 further multiplications in K. The claim follows directly from the above construction by counting the number of arithmetic operations in each step. Remark 3.1.1. Prior work on efficient Toom–Cook multiplication [5, 4] studied optimized evaluation and interpolation schemes, including fractional evaluation points such as ±1/2. In contrast, we restrict to integer evaluation points and postpone all divisions to a final scaling step, which simplifies the operation-count model over Fq and facilitates integration into the incomplete NTT framework. We also tested fractional evaluation points; after clearing denominators and applying the same addition-chain optimization, they required more additions/subtractions than the present choice. Thus, the set {0, ±1, ±2, 3, ∞} of evaluation points gives a simpler and cheaper interpolation schedule in our setting.
3.2
Hybrid multiplication over a residue ring
From now on, let q be an odd prime and set K = Fq . As in Section 2.2, let n = 2k , assume that 2ℓ+1 | (q − 1), and put Rq = Fq [x]/hxn + 1i. In this subsection, we instantiate the abstract cost function C(n; ℓ) in Theorem 2.2.1 by a concrete hybrid multiplication method over Rq . Recall that n is a power of 2 in our setting (Section 2.2). Throughout this subsection, let d denote the subproblem size; in particular, d = n/2ℓ is also a power of 2. Toom-4/Karatsuba hybrid. We apply Toom-4 recursively for L levels with Karatsuba multiplication as the base case. Let TM (d; L) and TA (d; L) denote the numbers of multiplications and additions/subtractions in Fq for multiplying two polynomials of degree less than d; the cost of the reduction modulo xd − ω is counted separately. By Proposition 1 and summing the
7
geometric series of the 54d-terms, we have Kar TM (d; L) = 7L TM (d/4L ) + (2d − 1)1L>0 ,
TA (d; L) = 7L TAKar (d/4L ) + 72d (7/4)L − 1 , Kar (d′ ) and T Kar (d′ ) denote the operation where 1L>0 = 1 if L > 0 and 0 otherwise. Here TM A counts of Karatsuba multiplication for input size d′ , estimated by (d′ )log2 3 and 8((d′ )log2 3 − d′ ) respectively. These counts follow from the standard recursive operation count for Karatsuba multiplication; see, e.g., the proof of Theorem 8.3 in [15]. Consequently we obtain
TM (d; L) = 7L (d/4L )log2 3 + (2d − 1)1L>0 , TA (d; L) = 7L · 8 (d/4L )log2 3 − d/4L + 72d (7/4)L − 1 . Incomplete NTT with Toom-4/Karatsuba hybrid. As in Subsection 2.2, let ℓ be the NTT depth. Following [10], let α and µ denote the costs of one addition/subtraction and one multiplication in Fq , respectively. We normalize by µ and put w := α/µ. For one subproblem of size d, define Cw (d; L) := TM (d; L) + w TA (d; L). (3.1) Substituting this into the cost formula (2.1) of Theorem 2.2.1 with d = n/2ℓ , we obtain the following weighted cost model: Cw (n; ℓ, L) = 2ℓ Cw (n/2ℓ ; L) + (3ℓn/2)(1 + 2w) + (2n − 2ℓ )1ℓ>0 + w(n − 2ℓ ),
(3.2)
where the last two terms account for the final scaling and the reduction modulo xn/2 − ζ22j+1 ℓ+1 in each CRT component. For a fixed triple (n, ℓ, w), only the first term in (3.2) depends on L. Therefore, for each pair (n, ℓ), the optimal recursion depth is obtained by minimizing (3.1) with d = n/2ℓ . ℓ
3.3
Parameter optimization and comparison
We evaluate the cost model in Subsection 3.2. To highlight the effect of multiplication algorithms, we fix w = 0.2 (i.e., µ/α = 5 as in [10]), which reflects a typical setting where additions/subtractions are cheaper than multiplications. For w = 0.2, Toom-4 becomes effective only for sufficiently large subproblems: Minimizing Cw (d; L) in (3.1) over L shows that the optimal recursion depth is L = 0 for d ≤ 128, L = 1 for d = 256, and L = 2 for d = 512, 1024. In particular, for d ≤ 128, the hybrid method reduces to pure Karatsuba. Since Karatsuba has a lower cost than schoolbook multiplication in our model for all parameter sizes considered here, we omit schoolbook from the comparison. We compare three multiplication strategies under the same NTT depth ℓ: Karatsuba (L = 0), pure Toom-4, and the proposed Toom-4/Karatsuba hybrid. Here, “pure Toom-4” means that Toom-4 is applied as long as possible and Karatsuba multiplication is used at the final base level. The maximal recursion depth is denoted by Lmax , while Lopt denotes the value minimizing Cw (d; L) in (3.1). The results for n ∈ {256, 512, 1024} are shown in Table 1. Table 1 shows that, for fixed ℓ, the proposed hybrid method consistently improves on pure Toom-4 and, for sufficiently small ℓ, also improves on Karatsuba. This suggests that, beyond previous analyses focusing mainly on schoolbook or Karatsuba multiplication, Toom-4 can provide additional gains in the limited-depth regime. As ℓ increases, the subproblem size d = n/2ℓ 8
Table 1: Weighted cost Cw (n; ℓ, L) with w = 0.2 and n ∈ {256, 512, 1024} for multiplication over Fq [x]/hxn + 1i. Here ℓ is the NTT depth, d = n/2ℓ is the subproblem size, and w = 0.2 is the relative cost of additions/subtractions. The columns correspond to Karatsuba (L = 0), pure Toom-4 (L = Lmax ), and the hybrid method (L = Lopt ). Costs are measured in units of one multiplication in Fq . n 256 512
1024
ℓ 0 1 0 1 2 0 1 2 3
d 256 128 512 256 128 1024 512 256 128
Karatsuba 16700.0 12061.2 50458.8 35497.2 25197.6 152093.6 105114.0 73144.8 52545.6
Toom-4 33851.0 20834.4 73945.8 69799.2 42744.0 246333.8 152088.0 141748.8 87638.4
Hybrid 15877.8 (Lopt = 1) 12061.2 (Lopt = 0) 44781.0 (Lopt = 2) 33852.8 (Lopt = 1) 25197.6 (Lopt = 0) 120521.4 (Lopt = 2) 93758.4 (Lopt = 2) 69856.0 (Lopt = 1) 52545.6 (Lopt = 0)
becomes smaller, and the optimal choice eventually becomes L = 0, so that the hybrid method coincides with Karatsuba. Thus, for parameter sets with large admissible NTT depths, such as the recommended parameters of Kyber, the improvement by Toom-4 is limited. In contrast, when the admissible depth is restricted by the 2-adic valuation of q − 1, the proposed hybrid yields a noticeable reduction in cost.
4
Experimental validation
We provide an experimental validation of the proposed hybrid method. The goal is not to obtain precise quantitative agreement with the theoretical cost model, but to confirm the qualitative behavior predicted in Section 3.3. All experiments were conducted on a standard laptop environment (Python 3, single-threaded); see [13] for details. We implemented incomplete NTT together with Karatsuba, pure Toom-4, and the proposed hybrid method. Polynomial multiplication is performed over Fq [x]/hxn + 1i with n ∈ {256, 512, 1024}. To make the limited-depth regime visible, we choose primes q of comparable size but with different 2-adic valuations of q − 1, which directly control the maximal admissible depth of incomplete NTT. For a prime q, the maximal admissible incomplete NTT depth is ℓmax = min{v2 (q − 1) − 1, log2 n}, where v2 (q − 1) denotes the 2-adic valuation of q − 1. While the case of Kyber was experimentally studied in [10], we choose NTT-unfriendly prime moduli (primes for which the admissible NTT depth is limited) of comparable size near the Dilithium modulus: q = 8380403, 8380381, 8380249, 8380369, for which ℓmax = 0, 1, 2, 3, respectively. For each (n, q), we apply incomplete NTT with depth ℓ = ℓmax , and report the median running time over 100 random inputs. Table 2 reports the running times. For each instance, the hybrid method uses the optimal recursion depth Lopt for the corresponding subproblem size. Note that when Lopt = 0, the hybrid method reduces to Karatsuba; this explains the identical entries in the corresponding rows. The results are consistent with the theoretical prediction. When the admissible NTT depth is very limited (e.g., ℓmax = 0), the hybrid method significantly outperforms Karatsuba.
9
Table 2: Running time (ms) for multiplication over Fq [x]/hxn + 1i. Here ℓmax = min{v2 (q − 1) − 1, log2 n} is the maximal admissible NTT depth, and d = n/2ℓmax is the subproblem size. For incomplete NTT with depth ℓ = ℓmax , we compare Karatsuba (L = 0), pure Toom-4, and the hybrid method (L = Lopt ). Each value is the median over 100 random inputs. n 256 512
1024
q 8380403 8380381 8380403 8380381 8380249 8380403 8380381 8380249 8380369
ℓmax 0 1 0 1 2 0 1 2 3
d 256 128 512 256 128 1024 512 256 128
Karatsuba 16.722 11.130 50.738 33.975 22.812 152.838 101.967 68.567 45.749
Toom-4 32.873 15.405 57.431 66.562 31.415 237.411 114.807 133.386 63.358
Hybrid 14.182 11.130 36.901 28.998 22.812 104.767 74.587 58.385 45.749
As the admissible depth increases, the advantage gradually diminishes, and eventually disappears when the subproblem size becomes too small. This supports the conclusion that the proposed method is mainly beneficial in the limited-depth regime of incomplete NTT. The implementation used for the experiments is publicly available at [13].
5
Conclusion and future work
In this paper, we presented a detailed complexity analysis of Toom-4 polynomial multiplication including constant factors, and integrated it into the incomplete NTT framework over Rq = Fq [x]/hxn + 1i. Based on this analysis, we derived explicit cost formulas and identified the optimal recursion depth in a weighted cost model. Our current implementation is in Python; however, the proposed cost model is independent of implementation details and is intended to guide optimized low-level implementations. Our results show that Toom-4 provides additional gains mainly in the limited-depth regime of incomplete NTT, where the admissible depth is restricted by the 2-adic valuation of q − 1. In particular, the hybrid method is most effective when the transform depth is minimal, highlighting a practically relevant regime where Toom-4 becomes advantageous. Future work includes optimized low-level implementations (e.g., in C or C++) and further evaluation in concrete lattice-based cryptographic schemes.
Acknowledgment The authors thank Masaya Yasuda for helpful comments. Preliminary results of this work were presented at the poster session of the 2026 Symposium on Cryptography and Information Security (SCIS 2026), a Japanese conference on cryptography and information security, where the authors received valuable comments and suggestions, particularly on hybridization with NTT. This work was partially supported by Comprehensive Research Organization, Fukuoka Institute of Technology. This work was also partially supported by JST CREST Grant Number JPMJCR2113 and JSPS KAKENHI Grant Number 25K00140. 10
References [1] National Institute of Standards and Technology: Encapsulation Mechanism Standard”, FIPS 203, 2024.
“Module-Lattice-Based
Key-
[2] National Institute of Standards and Technology: “Module-Lattice-Based Digital Signature Standard”, FIPS 204, 2024. [3] R. Agarwal and C. Burrus: “Fast Convolution using fermat number transforms with applications to digital filtering”, In: IEEE Transactions on Acoustics, Speech, and Signal Processing, 22, no. 2, pp. 87–97, 1974. [4] M. Bodrato, “Towards optimal Toom–Cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0”, In: Proc. WAIFI 2007, LNCS 4547, pp. 116–133, 2007. [5] M. Bodrato and A. Zanoni, “Integer and polynomial multiplication: towards optimal Toom– Cook matrices”, In: International Symposium on Symbolic and Algebraic Computation, ISSAC 2007, pp. 17–24, 2007. [6] J. Bos et al.: “CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM”, 2018 IEEE 10th EuroS&P, pp. 353–367, 2018. [7] S. A. Cook: “On the Minimum Computation Time of Functions”, PhD thesis, Harvard University, 1966. [8] J. W. Cooley and J. W. Tukey: “An Algorithm for the Machine Calculation of Complex Fourier Series”, Mathematics of Computation, 19, No. 90, pp. 297–301, 1965. [9] L. Ducas et al.: “CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme”, IACR Transactions on Cryptographic Hardware and Embedded Systems, Vol. 2018 (1), pp. 238– 268, 2018. [10] S. M. Hafiz et al.: “Incompleteness in Number-Theoretic Transforms: New Tradeoffs and Faster Lattice-Based Cryptographic Applications”, 2025 IEEE 10th EuroS&P, pp. 565–584, 2025. [11] A. Karatsuba and Y. Ofman: “Multiplication of many-digital numbers by automatic computers”, Proceedings of USSR Academy of Sciences, 145 (7), pp. 293–294, 1962. [12] Z. Liang and Y. Zhao: “Number Theoretic Transform and Its Applications in Lattice-based Cryptosystems: A Survey”, Cryptology ePrint Archive, Paper 2022/1682, 2022. [13] S. Oku and M. Kudo: “Implementation of Toom-4 Hybrid Multiplication for Incomplete NTT”, GitHub repository, https://github.com/Sakura-Oku/toom4_incomplete_ntt, 2026. [14] A. Toom: “The complexity of a scheme of functional elements realizing the multiplication of integers”, In: Soviet Mathematics-Doklady, 7, pp. 714–716, 1963. [15] J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013.
11