Types

nttConst

template<typename Precision>
struct nttConst

Bundles the three Montgomery constants derived from a runtime prime p: the prime itself, -p^{-1} mod R (n_dash), and R^2 mod p (r2). Callable from both host and device code.

Precision must be one of uint16_t, uint32_t, or uint64_t.

Precision p

The prime field modulus.

Precision n_dash

-p^{-1} mod R, where R = 2^(8 * sizeof(Precision)). Used as the Montgomery reduction constant.

Precision r2

R^2 mod p. Used to convert values into the Montgomery domain.

__host__ __device__ nttConst(Precision p)

Computes all three constants from p using Newton’s method (6 iterations) for n_dash and a double-width intermediate for r2.

Example

#include <ntt.hpp>

// Build constants on the host and pass to a kernel
const uint32_t prime = 998244353;
cupqc::nttConst<uint32_t> ntt_const(prime);

// ntt_const.p      == prime
// ntt_const.n_dash == -prime^{-1} mod 2^32
// ntt_const.r2     == (2^32)^2 mod prime

Like other host-side constants, ntt_const must be passed by value to CUDA kernels. Pass it to NTT::load_to_mont() and NTT::store_from_mont() (and their staged counterparts) to perform Montgomery domain conversions at load/store time when using a runtime prime.