Abstract
This work presents a tree-based FPGA architecture for evaluating univariate polynomials over the Mersenne-31 prime field F_p, where p = 2^31 - 1, a finite field used in modern zero-knowledge proof systems and STARK-oriented arithmetic. Instead of the serial dependency structure of Horner evaluation, the proposed method stores polynomial coefficients in bit-reversed order and evaluates them through a complete binary tree using the powers r, r^2, r^4, ..., r^(2^i) of the evaluation point.
For a polynomial with N coefficients, where N is a power of two, the construction requires exactly N-1 finite-field multiplications and N-1 additions, matching the arithmetic work of Horner's method while reducing the circuit dependency depth to log_2(N). This structure exposes parallelism that is particularly suitable for FPGA and hardware acceleration.
We provide independent implementations in Rust and synthesizable SystemVerilog and cross-validate the tree evaluator against conventional polynomial evaluation for correctness. FPGA RTL configurations with one, two, and four parallel processing units are investigated to characterize the scaling of the architecture. For N = 1024, the four-unit RTL configuration achieves a 3.89x reduction in simulated cycle count relative to the single-unit configuration.
The architecture is intended as a reusable hardware building block for finite-field polynomial computation, polynomial commitment schemes, STARK provers, Sumcheck-oriented accelerators, and other zero-knowledge proof systems requiring efficient arithmetic over Mersenne-31. The results demonstrate how tree-based polynomial evaluation can expose fine-grained hardware parallelism without increasing the asymptotic number of field operations.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
Mkhida, Ali Mr, "Tree-Based Evaluation of Univariate Polynomials over Mersenne-31 on FPGA", Technical Disclosure Commons, ()
https://www.tdcommons.org/dpubs_series/11944