1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// Copyright (C) 2024-2026 Vaea SAS
// SPDX-License-Identifier: AGPL-3.0-or-later
//
// This file is part of VaeaNTT.
//
// VaeaNTT is free software: you can redistribute it and/or modify it under
// the terms of the GNU Affero General Public License as published by the
// Free Software Foundation, either version 3 of the License, or (at your
// option) any later version.
//
// VaeaNTT is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public
// License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with VaeaNTT. If not, see <https://www.gnu.org/licenses/>.
//! # 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 for convenience
pub use ;
pub use ;
pub use Ntt64Context;