Module ntt64 

64-bit NTT Pipeline

High-performance Number Theoretic Transform for 60–62 bit NTT-friendly primes, targeting Fully Homomorphic Encryption (FHE) workloads and large-field lattice cryptography. All arithmetic is performed on u64 values with primes up to ~62 bits (strictly < 2⁶²).

Architecture

Modular arithmetic is provided via two complementary strategies:

• Barrett reduction (mod_mul_barrett) — division-free modular multiplication using a precomputed constant μ = ⌊2¹²⁸/q⌋. Used as the default reduction throughout the NTT butterfly loops.
• Montgomery reduction (mod_mul_mont) — efficient for long chains of multiplications in Montgomery domain (a·R mod q). Useful when the same element is multiplied many times before leaving the domain.

NTT butterflies follow the standard radix-2 split:

• Forward NTT — Cooley-Tukey Decimation-In-Time (DIT), layers from coarsest (gap = N/2) to finest (gap = 1).
• Inverse NTT — Gentleman-Sande Decimation-In-Frequency (DIF), layers from finest to coarsest, with a final N⁻¹ mod q normalization pass.

Twiddle ordering uses the Longa-Naehrig layout (as in SEAL and OpenFHE): twiddle factors are stored in bit-reversed order so that each butterfly layer accesses them sequentially, yielding good cache behaviour. The transform implements negacyclic convolution in Z_q[X]/(X^N+1) directly by folding the ψ (2N-th root of unity) factors into the twiddle table.

Quick Start

use vaea_ntt::ntt64::{Ntt64Arith, Ntt64Context, generate_primes_60};

// Generate one 60-bit NTT-friendly prime for N = 1024
let primes = generate_primes_60(1024, 60, 1);
let arith  = Ntt64Arith::new(primes[0]);
let ctx    = Ntt64Context::new(1024, arith);

let mut data = vec![0u64; 1024];
data[0] = 42;

// Forward NTT (polynomial → evaluation domain)
ctx.forward(&mut data);

// Inverse NTT (evaluation domain → polynomial)
ctx.inverse(&mut data);

assert_eq!(data[0], 42);
assert!(data[1..].iter().all(|&x| x == 0));

Pre-defined Primes

Constant	Value	Bits	Max N	Origin
PRIME_60_1	1 152 921 504 606 584 833	60	32 768	k·2¹⁶+1
PRIME_60_2	576 460 752 308 273 153	60	32 768	k·2¹⁶+1
PRIME_60_3	576 460 752 312 401 921	60	32 768	k·2¹⁶+1
PRIME_62_1	4 611 686 018 326 724 609	62	32 768	k·2¹⁶+1
PRIME_SEAL	0x1FFF_FFFF_FFE0_0001	61	1 048 576	2⁶¹−2²¹+1 (SEAL)

Use Cases

• FHE libraries — drop-in NTT for SEAL/OpenFHE-compatible prime towers (BFV, BGV, CKKS schemes).
• Large-field lattice crypto — any scheme requiring polynomial arithmetic in Z_q[X]/(X^N+1) with q up to ~62 bits.
• Multi-prime RNS — combine several 60-bit primes via the crate::rns module for coefficient moduli exceeding 64 bits.

Modules

• arith — Modular arithmetic (Barrett, Montgomery, add/sub)
• prime — Prime generation and primality testing
• context — NTT context with precomputed twiddle tables

Re-exports

pub use arith::from_montgomery;

pub use arith::mod_add;

pub use arith::mod_inv;

pub use arith::mod_mul_barrett;

pub use arith::mod_mul_mont;

pub use arith::mod_pow;

pub use arith::mod_sub;

pub use arith::to_montgomery;

pub use arith::Ntt64Arith;

pub use arith::PRIME_60_1;

pub use arith::PRIME_60_2;

pub use arith::PRIME_60_3;

pub use arith::PRIME_62_1;

pub use arith::PRIME_SEAL;

pub use prime::find_primitive_root;

pub use prime::generate_primes_60;

pub use prime::is_prime;

pub use context::Ntt64Context;

Modules

arith

64-bit Modular Arithmetic

context

NTT Context — Forward and Inverse Transforms

prime

Prime Generation and Primality Testing