NTT, CRT, and fast ring arithmetic

Status: current narrative. This page documents the implemented CRT and NTT paths, including the AVX-512IFMA exact cache.

Akita computes ring products by mapping each ring to several smaller prime fields. It performs a negacyclic NTT in each field, multiplies matching evaluations, applies an inverse NTT, and reconstructs the centered result with the Chinese remainder theorem. The same representation supports matrix matvecs over balanced signed digits.

The protocol fields and the CRT fields have different jobs. Protocol values live in the pseudo-Mersenne fields described in Field arithmetic. The smaller CRT primes are auxiliary compute fields chosen to provide roots of unity for each active ring degree. They do not change the statement being proved.

Deferred reduction and balanced digits

The commitment matvec first decomposes field coefficients into balanced base (2^L) digits. A digit has the exact interval

[ [-2^{L-1}, 2^{L-1}-1]. ]

Bases through (L=8) fit in i8. Bases from (L=9) through (L=16) fit in i16. The NTT cache selector receives the resulting absolute coefficient bound directly. It does not infer the bound from a label such as L10.

Code: crates/akita-algebra/src/ring/cyclotomic/decomposition.rs and crates/akita-types/src/ntt_cache/.

CRT and NTT representation

For a ring of degree (D), each CRT prime supplies a primitive root of order (2D). The forward transform multiplies by the negacyclic twist and then performs a decimation in frequency transform. The inverse performs the inverse decimation in time stages, applies the inverse scale, and removes the twist. The forward and inverse order avoids a separate bit reversal.

The ordinary production profiles use 30 bit CRT primes stored in i32 limbs:

The pointwise products and inverse transforms run independently for each CRT prime. Garner reconstruction then combines the residues into the protocol field. The optional prime 12289 is an exactness tail. It supports every protocol ring degree through D = 2048 and is added only when the base CRT product does not meet the requested bound.

What AVX-512 means in the current implementation

Akita has two different AVX-512 paths. They must not be described as one backend.

The ordinary i32 NTT path uses the scalar reference implementation or the runtime selected x86 implementation. AKITA_SCALAR_NTT=1 forces the scalar path. The x86 transforms are written once over a vector-width trait and instantiated at 256 and 512 bits. Both use radix-4 passes whose butterfly half length is at least 16, followed (forward) or preceded (inverse) by a 256-bit kernel that runs the last four or five stages in registers. Degrees below 64 use the scalar transforms. Runtime dispatch selects the AVX2 instantiation. AKITA_AVX512_NTT=1 opts into the 512-bit transforms and pointwise kernels on hosts with avx512f, avx512dq, and avx512bw. On the measured AMD Zen 4 host, whose 512-bit units are double-pumped, the 512-bit transforms were slower than AVX2 up to D256 and at most 2% faster at D1024, and single-threaded proving did not get faster, so they are not the default.

The second path is AVX-512IFMA. It is used for exact signed NTT caches, including selected dense q128 commitments whose digits fit in i8. The selector enables it only when all of the following hold:

• the process has avx512f, avx512dq, and avx512ifma;
• AKITA_SCALAR_NTT is not set to 1;
• the ring degree is D64 through D2048; and
• the exact cache request can be represented by the selected IFMA CRT product, with an optional exactness tail where that profile supports one.

The IFMA kernels use 512 bit vectors with eight u64 lanes. The instruction family uses a 52 bit radix internally. The selected CRT primes are each below (2^{50}), so the stored canonical residues are 50 bit values. They are NTT primes, not the protocol field moduli:

The exact cache uses the smallest CRT representation that meets the strict CRT bound:

For the full signed i16 bound, the one prime Q32 base is not sufficient at the eligible degrees, so Q32 exact caches use the mixed tail. The two prime Q64 base supports much larger widths without a tail. The three-prime Q128 base is roughly 150 bits. Adding 12289 raises the exact reach to roughly 163.6 bits and the 30-bit tail to roughly 180 bits, matching the portable six-prime profile. The 14-bit tail is preferred whenever it suffices: its transforms and pointwise products run at twice the SIMD lane count of the 30-bit tail. This is why one AVX-512IFMA host can use different cache representations for different field and schedule shapes.

This representation is used by ExactNegacyclic cache requests. Ordinary Negacyclic, Cyclic, and BothTransforms requests use the selected i32 profile. The exact selector uses the field modulus, ring degree, matrix width, and signed RHS bound. It does not select IFMA merely because the host has AVX-512.

Dense q128 commitments add one further performance rule. If the complete row exceeds the three-prime IFMA capacity but fits after adding a tail, an eligible AVX-512IFMA host accumulates the row exactly. This avoids repeatedly transforming and reconstructing many small chunks. Scalar, AVX2, and NEON hosts keep the chunked i8 path, which is faster and uses less prepared-cache memory on those architectures. The rule depends on CPU capability and the capacity bound, not on a machine name or a fixed problem size.

The IFMA matrix stores one transformed negacyclic matrix for each selected 50 bit prime. When a Q128 tail is needed, the cache stores a shorter prefix of the same matrix under 12289, or under the 30 bit prime 1073707009 when base plus 12289 is insufficient. The matvec transforms the signed i16 RHS, accumulates pointwise products, reconstructs with all selected residues, and returns canonical protocol field elements. The tail does not change setup bytes, proof bytes, transcript bytes, or setup digests.

Code: crates/akita-algebra/src/ntt/ifma52.rs, crates/akita-algebra/src/ntt/ifma52/x86.rs, crates/akita-types/src/ntt_cache/exact.rs, and, for the tail transforms, crates/akita-algebra/src/ntt/avx/transform.rs.

Accumulation capacity and chunking

Let q be the protocol field modulus, D the ring degree, W the number of matrix columns accumulated before reconstruction, B the maximum absolute value of a signed RHS coefficient, and P the product of the active CRT primes. Each output coefficient is a signed sum of at most D products per matrix column. The strict condition for centered reconstruction is

2 * W * D * floor(q / 2) * B < P

If the base product does not satisfy this condition, exact preparation adds the 12289 tail when the combined product does satisfy it. If neither product is sufficient, preparation rejects the request. The same capacity calculation is used by cache preparation, verifier warming, runtime matvec checks, and tests.

Large matrix operations can split their work into chunks and reconstruct after each chunk. This keeps every intermediate result inside the same bound. The cache key records the ring degree, transform domain, and required prefix. A stronger exact request can retain a tail prefix for a later weaker request.

On portable, AVX2, and NEON hosts, exact caches use the field selected i32 profile and add the 12289 tail when needed. On eligible AVX-512IFMA hosts, the selector may use the 50 bit u64 profiles described above. These are different storage choices for the same centered CRT contract.

Code: crates/akita-algebra/src/ntt/crt.rs, crates/akita-types/src/ntt_cache/, and docs/crt-ntt-capacity-profile.md.

Limb-split exact products

A field-sized CRT product pays for the full width of every matrix entry. For a q128 exact product that is six i32 primes, plus a tail, or three IFMA primes. Each prime costs one RHS transform per column and one pointwise product per output row. When a matrix has only a few output rows, the RHS transforms dominate, and a narrower representation is cheaper.

A prover exact cache can therefore store each public entry as balanced limbs. Let (n) be the bit length of (q). A centered entry (A), with (|A| < q/2), is written as

[ A = \sum_{l=0}^{L-1} 2^{bl} A_l, \qquad |A_l| \le 2^{b-1}, \qquad bL \ge n + 1. ]

Each limb row accumulates exactly under two CRT primes. The capacity condition above applies with (2^b) in place of (q), so the limb bound replaces the field bound. Portable, AVX2, and NEON hosts use the two i32 Q32 primes. Eligible AVX-512IFMA hosts use the first two 50 bit IFMA primes. The matvec reconstructs every limb product (y_l = A_l \cdot v) as an exact integer and returns (\sum_l 2^{bl} y_l) in the protocol field.

The selector picks the smallest (L \ge 2) whose limbs fit the two-prime capacity. At the q128 modulus with (D = 512), a width of 1536, and an 11 bit signed digit, the i32 primes need (L = 5) limbs of 26 bits. The IFMA primes need (L = 2) limbs of 65 bits.

The limb form transforms the RHS under two primes instead of the full CRT set. It also computes (L) times as many pointwise products per output row. The selector compares both plans in units of one prime-row pointwise product. It charges 6 units for an i32 prime transform and 2 units for an IFMA prime transform. It uses limbs only when their estimated cost is strictly lower. With these weights, limbs win for few-row q128 and q64 products and lose once many rows share each RHS transform. The q32 base product uses only two i32 primes and a tail, so at the example shape limbs win only for a single row.

Limbs also change the memory footprint:

The limb form is used only for prover caches prepared without a verifier tail prefix. Verifier warmed caches, compression caches, and the prepared verifier artifact keep the base representation. The choice therefore changes prover time and prepared-cache memory, but not setup bytes, commitment bytes, proof bytes, transcript bytes, or setup digests.

Code: crates/akita-types/src/ntt_cache/limbs.rs and crates/akita-types/src/ntt_cache/exact.rs.

Smooth-subgroup FFT for Reed--Solomon encoding

The CRT transforms above accelerate multiplication in (\mathbb F_q[X]/(X^D+1)). Reed--Solomon encoding is a different operation: it evaluates a polynomial at many points in the protocol field itself.

The production fp128 modulus

[ q=2^{128}-2^{32}+22537 ]

was chosen in part because (q-1) contains the smooth factor

[ 17496=2^3\cdot 3^7. ]

primitive_nth_root::<F>(n) checks that n is positive and divides the configured smooth subgroup order, then derives a root of order n from the field's configured generator. Invalid requests panic.

SmoothDomain::new(omega, n) takes that caller-supplied root and size, factors the size, and precomputes the execution plan. Its primitivity check is a debug assertion; it does not provide production validation of an arbitrary supplied root. Construction can panic, including when omega is zero or n is not invertible in the field.

Other protocol fields do not implement SmoothFftField merely because they are pseudo-Mersenne fields.

Iterative mixed-radix execution

For

[ n=f_0f_1\cdots f_{s-1}, \qquad f_i\in{2,3,5,7}, ]

the forward transform first applies the mixed-radix analogue of bit reversal. It then sweeps the stages from small to large, running an in-place radix- (f_i) butterfly at each stage. The inverse uses inverse roots and multiplies the result by (n^{-1}).

The domain precomputes both digit-reversal positions and stage twiddles. Repeated encoding therefore performs no factorization, root search, or per-stage allocation. A reusable workspace holds the two transform buffers.

Small-radix kernels

Each butterfly has a specialized kernel. Radix 2 is the ordinary sum and difference. Radix 3 uses (1+\omega+\omega^2=0) to reduce the number of field multiplications. Radix 5 and radix 7 use precomputed Winograd constants and fixed addition chains instead of a dense quadratic-size DFT.

The configured fp128 subgroup uses only radices 2 and 3. Radix-5 and radix-7 kernels are implemented, but the current tests do not exercise them. Direct-DFT comparisons cover the selected sizes 2, 3, 6, 8, 9, 18, 24, 27, 54, 81, 162, 243, 486, and 729. Separate tests check root orders at selected sizes through 17496, forward/inverse round trips at 243, 1458, and 2187, and coset extension from 243 to 2187. These checks do not establish parity for every subgroup divisor.

Coset extension

Suppose evaluations are known on a subgroup of size (k), and the target Reed--Solomon domain has size (kB). The implementation first applies the inverse size-(k) transform to recover coefficients. For each of the remaining (B-1) cosets, it multiplies coefficient (i) by a coset shift raised to (i), then applies the forward size-(k) transform. The output is stored in coset-major order.

This flow reuses one SmoothDomain and one workspace across all cosets. It returns only the k(B-1) evaluations on the additional cosets; the original subgroup evaluations are not repeated. The smooth FFT and Reed--Solomon extension are exported arithmetic utilities currently exercised by unit tests and crates/akita-pcs/benches/fft_smooth.rs. The production prover and verifier do not call this encoding path.

Code: crates/akita-algebra/src/fft.rs.

Further reading

• specs/large-digit-ntt-infrastructure.md records the implemented exact signed digit and terminal NTT contract.
• book/src/usage/profiling.md documents the NTT matvec benchmarks and their cache labels.
• docs/crt-ntt-capacity-profile.md records the generated portable i32 capacity table. It does not replace the host dependent IFMA rules on this page.