cuPQC-NTT: Number Theoretic Transform

The cuPQC-NTT library provides GPU-optimized implementations of the Number Theoretic Transform (NTT) designed for direct integration into CUDA kernels. The NTT is the modular-arithmetic analogue of the Fast Fourier Transform and is a core building block of lattice-based cryptography, zero-knowledge proof systems, and modular ring arithmetic over finite fields. As a device-side library, cuPQC-NTT integrates directly into your CUDA kernels, enabling you to fuse NTTs with other GPU computations for maximum performance. Transforms run in the Montgomery domain; convert at load/store boundaries and convert twiddle tables once before reuse.

The notation in the panel below is used throughout the rest of this page for transform lengths and two-pass tiling.

Notation for N, M, K, and d

Transform length N is a power-of-two, with N =2d and d = log₂(N).

Sub-transform size M (a power-of-two) is set with SubSize<M>; K = N/M.

NTT Transform Modes

The cuPQC-NTT library provides two execution modes:

• Standard NTT: A complete N-point transform is performed in a single kernel launch per length-N buffer, with the full working set held in shared memory. This mode is ideal for transform lengths that fit within available shared memory.

• Staged NTT: For large N, per-block shared memory cannot hold the full workspace for an N-point transform in a single pass, so a staged NTT is required. With SubSize<M> and two kernel passes: the first stage runs M parallel K-point contiguous NTTs (K = N/M); the second runs K parallel M-point strided NTTs. Each stage limits the per-block working set to max(K, M) elements, enabling transforms that would not fit in a single block’s shared memory.

Supported Configurations

The table below summarizes the supported Execution Modes, Transform Type, Prime Fields, and Precomputed Roots.

Aspect	Summary
Execution modes	Standard: One-kernel transform of length-N. Staged: Two-kernel transforms of (N, SubSize<M>) pairs.
Transform type	Cyclic: Length-N transforms for arithmetic in the cyclic polynomial ring (modulo xN - 1).
Prime field	Custom: User-selected prime p < 262. Built-in: BabyBear / KoalaBear.
Precomputed roots	BabyBear / KoalaBear: *_primitive_root_S (10 ≤ S ≤ 24).

See Prime Field Constants for built-in prime values and compile-time root symbols.

Both Standard NTT and Staged NTT support uint16_t, uint32_t, and uint64_t as precisions for any prime modulus. The next two subsections tabulate supported transform-size limits for Standard NTT and Staged NTT.

Standard NTT Limits

The table lists Standard NTT (single-kernel) limits on transform length N and exponent d. Coefficients and the modulus use the same type width (for example both uint32_t) for each prime and coefficient-width row.

Prime	Width (precision)	Transform Size (N =2d)
Custom p	uint16_t	2 ≤ d ≤ 14
	uint32_t	2 ≤ d ≤ 13
	uint64_t	2 ≤ d ≤ 13

Staged NTT Limits

The table lists Staged NTT (two-kernel) limits, pairing each supported transform length N with allowed SubSize<M> values.

Transform Size (N =2d)	Allowed Sub-transform Size (SubSize<M>)
14 ≤ d ≤ 21	256 · 512 · 1024 · 2048 · 4096 · 8192
d = 22	512 · 1024 · 2048 · 4096 · 8192
d = 23	1024 · 2048 · 4096 · 8192
d = 24	2048 · 4096 · 8192

Key Features

• High Performance: GPU-optimized NTT kernels exploit shared memory and warp-level parallelism for maximum throughput.

• Montgomery Domain: Device transforms operate on Montgomery-domain data, with conversion at load/store (load_to_mont / store_from_mont and staged counterparts); twiddle tables are converted once before reuse.

• Cyclic Transforms: Implements the cyclic NTT for rings modulo xN - 1.

• Flexible Field Support: Supports user-selected primes up to 62-bit and built-in primes BabyBear / KoalaBear.

• Staged Transforms: The SubSize<M> operator enables memory-efficient transforms at large N by decomposing them into two kernel passes.

• Reusable Twiddle Tables: Twiddle factors are computed once and reused across an entire batch, minimizing startup overhead.