Paper 2026/1494

On $k$-way split multiplication algorithms

Abstract

Efficient polynomial multiplication and matrix-vector operations are fundamental to computational algebra and modern cryptography. In lattice-based post-quantum cryptography (PQC), schemes utilizing Number Theoretic Transform (NTT)-unfriendly rings require highly optimized subquadratic multiplication algorithms. In this paper, we establish a rigorous mathematical framework for generalized $k$-way split polynomial multiplication and Toeplitz Matrix-Vector Product (TMVP) algorithms over arbitrary fields. First, we construct generalized $k$-way Schoolbook and Karatsuba multiplication algorithms, deriving exact closed-form recurrence relations and arithmetic complexities for any integer $k$. Second, we introduce a novel $k$-way TMVP algorithm utilizing optimal evaluation points and matrix row-reversal techniques. We mathematically prove that this generalized formulation strictly achieves the theoretical interpolation lower bound, requiring exactly $2k-1$ subproblems and yielding a subquadratic asymptotic complexity of $O(n^{\log_k(2k-1)})$. Furthermore, we determine the optimal consecutive application sequence of $k$-way Karatsuba and Schoolbook algorithms for any input size $n$, proving that the peak efficiency is driven entirely by the prime factorization of $n$. Finally, we establish exact algebraic crossover thresholds, demonstrating that our generalized TMVP formulas and optimal algorithmic sequences significantly outperform state-of-the-art unequal $k$-way splits and classical combinations in the literature, providing minimum arithmetic operation counts for $k \in \{5, 6, 8, 12\}$ and inputs of power-of-two and power-of-three dimensions.