A team of researchers from academic and research institutions has released a new study detailing a systematic method for optimizing polynomial multiplication over finite fields, a critical operation underpinning both classical and emerging post-quantum cryptographic standards. The paper, titled "DP-Guided Schedule Selection for $mathbbF_2[x]$ Multiplication across ISAs," was authored by Junyu Zhou, Xiao Lan, and Hao Ren from Sichuan University, Jing Wang from the Huazhong University of Science and Technology, independent researcher Weiran Liu, and Si Gao from the Institute of Software at the Chinese Academy of Sciences.
The research addresses a persistent performance bottleneck in cryptographic software engineering. Efficient multiplication over the finite field $mathbbF_2[x]$—often referred to as carry-less multiplication—serves as a core primitive across a vast array of cryptographic systems. As modern computing landscapes shift and architectures such as ARM and RISC-V gain prominence alongside traditional x86 processors in open-source cryptographic libraries like OpenSSL and liboqs, developers face the complex challenge of retuning arithmetic kernels across a wide and fragmented range of Instruction Set Architectures (ISAs).
To achieve high performance, modern arithmetic libraries typically rely on recursive decomposition strategies, most notably Karatsuba- and Toom-Cook-style multiplication algorithms. These rules work by recursively splitting large operands into smaller subproblems, computing the individual products, and then recombining them. The complete sequence of recursive rule choices, tracing a path from the top-level multiplication down to the most fundamental base kernels, forms what researchers call a decomposition schedule.
However, finding the optimal schedule is far from trivial. The study notes that traditional hand-tuned schedules often fail to identify the most efficient decompositions when dealing with larger operand sizes. Furthermore, because different hardware architectures assign vastly different performance costs to basic operations like base multiplications, bitwise exclusive-or (XOR) operations, memory traffic, and recursive overhead, cross-platform retuning becomes an exceptionally labor-intensive task.
To overcome these hurdles, the research team formulated recursive $mathbbF_2[x]$ multiplication as an advanced schedule-selection problem. They discovered that the recursive rule space possesses a crucial mathematical property known as optimal substructure. This characteristic allows the application of dynamic programming, commonly abbreviated as DP, operating over a compact and precise ISA profile. This profile systematically accounts for the fundamental costs associated with base multiplication, XOR instructions, memory movement, and recursive overhead on any given target architecture.
Rather than relying on tedious trial-and-error or costly empirical benchmarks for every possible input size on every hardware platform, the DP-guided approach materializes the resulting optimal schedules directly as dispatch tables or fixed-size kernels. The researchers put their methodology to the test across a diverse array of hardware platforms, encompassing x86-64, ARM64, RISC-V64, and the microcontroller-class RP2040.
The evaluation demonstrated that the dynamic programming cost models accurately track runtime performance trends across varying input sizes. When deployed across the tested rule sets, the approach achieved consistent geometric mean speedups ranging from $1.04$ to $1.18$ times over gf2x, a widely used software library for polynomial arithmetic over $mathbbF_2[x]$.
The practical impact of this optimization extends well beyond standalone arithmetic benchmarks. The research team integrated their generated schedules into implementations of HQC and BIKE, two prominent code-based post-quantum cryptography candidates currently navigating the standardization landscape. Evaluated across three distinct 64-bit platforms, the integrations yielded end-to-end speedups ranging from $1.06$ to $1.21$ times for HQC, and an even more pronounced $1.01$ to $1.70$ times speedup for BIKE compared to their respective platform baselines. The researchers also evaluated the performance implications for Classic McEliece, another major post-quantum cryptographic scheme.
A significant practical advantage highlighted in the paper is the efficiency of the selection process itself. By utilizing pre-prepared architectural profiles, the schedule selection procedure for HQC and BIKE completes in a fraction of a second—taking between $0.075$ and $0.762$ seconds. This eliminates the traditional requirement of compiling numerous candidate implementations and executing time-consuming benchmarks during the search phase.
Ultimately, the research provides a robust, systematic alternative to traditional hand-tuning and measurement-driven empirical searches that evaluate performance per input size. By shifting the burden to a dynamic programming framework guided by hardware profiles, the new methodology significantly reduces the engineering effort required to port, optimize, and retune carry-less multiplication kernels across an increasingly diverse ecosystem of computing architectures.
