Concrete-NTT是一个纯Rust高性能数论变换库，用于处理大小为2的幂的向量。

该库提供了三种类型的NTT

• 素数NTT在$\mathbb{Z}/p \mathbb{Z}$域中计算变换，其中$p$是素数，允许对多项式模$p$进行算术运算。
• 本地NTT在内部使用多个素数计算第一种类型的变换，允许模拟模这些素数的乘积的算术运算，并在需要逆变换时截断结果。只要完整的整数结果绝对值小于所有素数乘积的一半，截断的结果将保证与使用环绕算术进行计算相同。它保证适合乘以任意系数的两个多项式，并以环绕算术返回结果。
• 本地二进制NTT类似于本地NTT，但针对乘法操作数中的一个操作数的系数在$\lbrace 0, 1 \rbrace$的情况进行了优化。

Rust要求

Concrete-ntt需要Rust版本>=1.67.0。

功能

• std (默认): 这将启用运行时架构检测以加速SIMD指令。
• nightly: 这将启用不稳定Rust功能以进一步加快NTT的速度，通过在支持AVX512指令的CPU上启用AVX512指令。此功能需要nightly Rust工具链。

示例

use concrete_ntt::prime32::Plan;

const N: usize = 32;
let p = 1062862849;
let plan = Plan::try_new(N, p).unwrap();

let data = [
    0, 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,
];

let mut transformed_fwd = data;
plan.fwd(&mut transformed_fwd);

let mut transformed_inv = transformed_fwd;
plan.inv(&mut transformed_inv);

for (&actual, expected) in transformed_inv.iter().zip(data.iter().map(|x| x * N as u32)) {
    assert_eq!(expected, actual);
}

更多示例可以在examples目录中找到。

• mul_poly_prime.rs：使用素数模数的非循环多项式乘法。使用以下命令运行示例：cargo run --example mul_poly_prime。
• mul_poly_native.rs：使用本地模数的非循环多项式乘法（2^32，2^64 或 2^128）。使用以下命令运行示例：cargo run --example mul_poly_native。

基准测试

可以使用以下命令执行基准测试：cargo bench。如果可用夜间构建工具链，则可以通过传递 --features=nightly 标志启用 AVX512 加速。