CS Paper Radar

FoldNTT: A Multiplier- and Twiddle-Lean NTT Core with Formally Verified Arithmetic for Proth Primes

Masato Kamba

cs.CR ·submitted 2026-09-06 06:09 UTC · v1

Abstract

Hardware for lattice-based post-quantum cryptography spends a large share of its area on the number-theoretic transform (NTT), dominated by modular multipliers and twiddle storage. FoldNTT is a redesign of the released radix-2 CFNTT accelerator (TCHES 2022) for the Falcon / FN-DSA prime q = 12289 with one hardware multiplier per butterfly instead of three and about half the stored twiddle constants. The Proth shape q = 3*2^12 + 1 turns modular reduction into shift-and-add K-RED folds, and the bit-reversed twiddle table obeys w[N/2+j] = psi*w[j], so half the table is derived without a multiplier. Checking the released RTL against the mathematics also exposed a bug: its inverse transform omits a per-stage halving and returns 2^10*x, which the retrofit corrects. Every arithmetic block is proven by exact-width SMT and compositional SymbiYosys proofs, control-safety invariants by k-induction; the proofs are mutation-tested and the composed transform is validated by simulation, all rerun by CI. On Artix-7 in a fully open flow, the retrofit costs 3->1 DSP48 per butterfly and -50% stored twiddle bits at a whole-core Fmax cost of about 4% (best of three seeds; within the seed-to-seed spread), measured on the released datapath driven by a controller we reconstructed (the reference FSM was never released) and validated by full-core simulation; a sequential core with our own controller builds to a timing-gated Basys-3 bitstream.

Closest papers

Nearest neighbours by meaning across the whole index.

Implementation and Evaluation of NTT Arithmetic for ML-KEM on a CGLA

cs.AR ·2026-09-24 ·Takuto Ando, Yasuhiko Nakashima
hot direction similarity 0.62
Abstract · Accepted as a Regular Paper for the WICS Workshop at CANDAR 2026

FIPS 203 standardizes ML-KEM for post-quantum key establishment. Its polynomial multiplication relies on NTT butterflies with exact modular arithmetic over q = 3329. Dedicated NTT accelerators minimize latency with fixed modular arithmetic and stage schedules. A CPU-Grounded Linear Array (CGLA) reuses one programmable linear datapath across several workloads. Mapping the transform to this datapath requires exact FP32 reconstruction and explicit stage transitions across the ARM-to-CGLA interface. We implement an eight-stage cyclic radix-2 driver over the ML-KEM modulus by splitting each twiddle into 8-bit and 4-bit parts before modular reduction. This driver differs from the standardized seven-layer incomplete negacyclic NTT and does not implement the full ML-KEM polynomial multiplication path. The arithmetic sequence keeps every integer below 2^24. One 41-PE call fuses the first two radix-2 stages, and six 47-PE calls execute the remaining stages while scattering outputs into next-stage records. Across four cohorts, 105 FPGA runs match all 817152 output coefficients. At batch size 64, measured FPGA end-to-end latency is 27.5 us per NTT, and the ASIC projection is 6.74 us. With PE gating, projected ASIC system energy is 10.1 uJ per NTT at batch size 8 and 58.9 uJ at batch size 64.

0.36

Reduction Modulo Binary Polynomials with Logarithmic Feedback Depth

cs.SC math.NT ·2026-09-08 ·Junyu Zhou, Kaiyi Zhang
similarity 0.58
Abstract

Polynomial modular reduction is central to binary finite-field arithmetic and repeated Frobenius powering. Top-down shift/XOR folding can use few operations when the nonleading support is sparse, but a tap near the leading term creates a long feedback chain. We formulate this recurrence as inversion of a nilpotent shift operator and factor its inverse by characteristic-two Frobenius powers. The resulting Frobenius-factorized reduction (FFR) applies to every monic binary modulus without materializing a reciprocal or dense reduction matrix, and its shifts can be generated online without a persistent modulus-specific schedule. For degree $m$ and nonempty nonleading support of size $s$, with nearest-tap distance $Δ_{\min}$, FFR uses exactly $\lceil\log_2(m/Δ_{\min})\rceil$ sequential feedback stages and has scheduled work $O(ms(1+\log(m/s)))$. A portable-C evaluation on 1,096 supports through degree $131072$ identifies distinct FFR, López--Dahab, and gf2x-backed Barrett regions. On four certified irreducible moduli, FFR makes complete Rabin irreducibility testing $1.35$--$8.04$ times faster than NTL and $1.60$--$6.81$ times faster than the matched Barrett implementation.

0.23

Scrambled Multiply-with-Carry Pseudorandom Number Generators

cs.CR cs.MS ·2026-10-19 ·Sebastiano Vigna
similarity 0.57
Abstract

Multiply-with-carry (MWC) generators are very fast pseudorandom number generators whose quality depends on the choice of a multiplier, and is usually assessed by applying the spectral test to an associated multiplicative congruential generator. The special form of the modulus is shown to impose structural limitations on the lattice structure of every MWC generator, which the generalized MWC generators of Goresky and Klapper mitigate; in the tests reported, a scrambler made of a single xor removes them. Since these limitations make the usual worst-case criterion useless, candidates are ranked by a weighted geometric mean of their figures of merit, which does not depend on their normalization, and multipliers are suggested for generators with 64 to 256 bits of state. Along the way, some errors in the literature are corrected. In the end, MWC192X is proposed: a 64-bit generator with 192 bits of state that passes all known tests, and emits an output in half a nanosecond. Analogous 32-bit generators are proposed for GPUs.

0.26

Discovering state-of-the-art quantum circuits with large language models

cs.AI quant-ph ·2026-10-15 ·Andi Gu, Alek H. Kemeny, Susanne F. Yelin, Mikhail D. Lukin
highly cited similarity 0.56
Abstract · 46 pages, 10 figures, 6 tables

Significant efforts are currently being directed toward the implementation of large-scale quantum information processors, but realizing useful quantum advantage also requires the development of efficient quantum algorithms. While for many practical problems the dominant resource costs are associated with a small set of computational primitives, optimizing them in the quantum setting presents unique challenges, including a reversibility constraint absent from ordinary classical computation. Here we introduce an evolutionary framework in which large language models (LLMs) propose circuit designs and an independent evaluator verifies and scores them. We apply this framework to tasks spanning numerical computation, chemistry, optimization, quantum simulation, and number theory. In seven of the eight tasks, the discovered circuits significantly reduce both Toffoli and qubit counts relative to the state of the art. In the eighth, the search discovers a new reversible architecture for prime-field modular inversion. By handling reversibility differently, the architecture makes divsteps -- a classical algorithm previously impractical for reversible integer arithmetic -- viable and substantially improves the Toffoli-qubit trade-off for modular inversion. These results open the door for evaluator-guided LLM co-design of new algorithmic structures for quantum computation.

0.38

Exact quantum splitting and the structure of finite algebras

cs.CC quant-ph ·2026-08-31 ·Muhammad Imran
similarity 0.56
Abstract

For squarefree $f\in\F_q[x]$, Berlekamp's fixed-point algebra is $B\cong\F_q^r$, where $r$ is the number of irreducible factors. We give an exact quantum splitting procedure in a circuit model permitting efficiently computable, input-dependent single-qubit rotations. For a block with $s\ge2$ factors, a quadratic-character test (odd $q$) or absolute-trace test (characteristic $2$) is nonconstant with an exactly known probability $p_{q,s}\ge1/2$. Its value depends only on $q,s$, not on the hidden factors. An auxiliary-qubit reduction to success probability $1/4$ makes one Grover iteration exact. Thus factorization takes exactly $r-1$ splitting rounds and $O(n^3\log q)$ quantum $\F_q$-operations, with deterministic polynomial classical preprocessing and bookkeeping. The method also extracts primitive idempotents of arbitrary finite-dimensional commutative unital algebras given by structure constants in $O(n^4\log q)$ quantum $\F_q$-operations, staying over $\F_q$ throughout. Computing the radical and passing to the center extends it to the decomposition of $A/\Rad(A)$ into simple two-sided ideals, for an arbitrary finite-dimensional associative $\F_q$-algebra $A$.

0.27

Shift-Accumulate Attention: Multiplier-Free Query--Key Products for Transformer Decoding

cs.AR ·2026-09-05 ·Khubaib Ahmed, Amna Noor, Ahsan Ul haq
similarity 0.55
Abstract

Power-of-two (PoT) quantisation turns a multiplication into a bit shift, so far only for the post-softmax attention--value product. The earlier and larger product, S=QK^T, has not been reformulated the same way. We quantise the key cache to a signed power-of-two fixed-point code, so that every scalar multiplication in QK^T becomes a sign flip, a bit shift and an integer accumulation. A fixed-point head-room F>= e_max turns every shift index r=F-e into a non-negative left shift, making the accumulation exact in integer arithmetic. We add a sub-power mantissa extension that halves the score error for one extra shift-add, a shift-exact online softmax whose running maximum lives in an integer log2 domain so that every rescaling is itself an exact shift, and a log-quantised AV product. Fused CUDA kernels in a 1.1B Llama decoder on an RTX 4090: at B=8, T=32k the 4-bit kernel is 4.60x faster than FP16 scaled dot-product attention with a 2.5x smaller KV cache, and batched decoding crosses over at B=64 to 1.22x FP16 throughput at 11.02 against 13.77 GB peak memory. A matched INT8 multiply--accumulate kernel on the same tiling reaches 5.29x: on a GPU with a hardware 4-way INT8 dot product, shift-accumulate is not faster than the MAC it replaces. An iso-storage control--an 8-bit shift code of exactly one byte per key, run through the identical kernel--prices the arithmetic substitution alone at 2.02x at comparable accuracy. The advantage of the PoT representation is therefore its density and the removal of the multiplier, not raw GPU throughput. A sweep over exponent width, mantissa levels, granularity and rounding gives the design lesson: nearest-PoT relative error is scale-free, so extra exponent bits buy nothing (eps_S=0.1302 at 3, 4 and 5 bits) and accuracy must come from mantissa terms.

0.16

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

cs.CC quant-ph ·2026-11-04 ·Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh
similarity 0.54
Abstract · 16 pages

In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs $O(q^2)$ gates (and $O(q)$ qubits) to perform the exact Fourier transform over $\mathbb{F}_{2^q}$. Cleve and Watrous (FOCS 2000) improved this gate count to $O(q (\log q)^2 (\log \log q))$ using the integer multiplication algorithm in $O(n (\log n) (\log \log n))$ time for two $n$-bit integers (best known at that time). Our first main result shows that this gate count can be improved to $O(q (\log q))$. In fact, if there is a multiplication circuit, to multiply two $n$-bit integers, with $O(n (\log n)^α)$ gates; we get a QFT circuit with $O(q (\log q)^α)$ gates (improving upon $O(q (\log q)^{α+ 1})$) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with $o \left( q (\log q)\right)$ gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with $O \left( q (\log \log(q/\varepsilon))^{α+1} \right)$ gates, where $ε$ is the approximating parameter. Our second main result again improves this to $O \left( q (\log \log(q/\varepsilon))^α \right)$ gates.

0.25

Faster PMNS Multi-precision Multiplications Using Truncated Montgomery Technique

cs.CR ·2026-10-07 ·Laurent-Stéphane Didier, Alexy Dutois-Ruiz, Jean-Marc Robert
similarity 0.54
Abstract · 21 pages, one figure

The Polynomial Modular Number Systems (PMNS) aim to represent elements of fields or rings of large characteristics using polynomials satisfying bounds on some parameters (degree, absolute values of the coefficients). Those PMNS, while some conditions are fulfilled, using convenient parameters and implementation features, allow some speed-ups in cryptographic computations. Recent works (Meloni \emph{et al.} \cite{MeloniPV25}) propose better speed-ups by improving the parameter generation of the system, and by using multi-precision polynomial coefficients, i.e. coefficients stored using several machine words. In this work, we first present PMNS schoolbook software implementation better in some context than the Toeplitz state-of-the-art counterpart of \cite{MeloniPV25}, taking advantage of smaller memory cost by being free to choose a smaller $n$ parameter, minimizing at the same time the complexity of the multiplication. This implementation for 4096 bit modulo size shows element size smaller by 11\% and 20 \% speed-up. We thus present a new improvement on the PMNS, applying to the \textsl{internal reduction} an approach similar to the truncated Montgomery reduction technique presented by Didier \emph{et al.} in \cite{DidierEGR24}. In the context of software implementations using \texttt{AVX512} instruction set extension, and modulo size up to 8192 bits, this new approach allows speed-ups up to 15\% in modular multiplication computation, in comparison with conventional approaches.

0.26