mod compute;
#[cfg(test)]
mod tests;
use crate::error::{BarracudaError, Result};
use crate::tensor::Tensor;
pub struct FheNtt {
input: Tensor,
degree: u32,
modulus: u64,
root_of_unity: u64,
barrett_mu: u64,
twiddle_factors: Vec<u64>,
pipeline_butterfly: wgpu::ComputePipeline,
pipeline_bit_reverse: wgpu::ComputePipeline,
bind_group_layout: wgpu::BindGroupLayout,
}
impl FheNtt {
pub fn new(input: Tensor, degree: u32, modulus: u64, root_of_unity: u64) -> Result<Self> {
let expected_size = (degree as usize) * 2; if input.len() != expected_size {
return Err(BarracudaError::Device(format!(
"Input length {} doesn't match expected {} (degree {} * 2)",
input.len(),
expected_size,
degree
)));
}
if degree < 2 || !degree.is_power_of_two() {
return Err(BarracudaError::Device(format!(
"Degree {degree} must be a power of 2 ≥ 2 for NTT"
)));
}
if modulus == 0 {
return Err(BarracudaError::Device(
"Modulus must be non-zero".to_string(),
));
}
if !(modulus - 1).is_multiple_of(2 * degree as u64) {
return Err(BarracudaError::Device(format!(
"Modulus {modulus} must satisfy q ≡ 1 (mod 2N) where N={degree}"
)));
}
let barrett_mu = u64::MAX.checked_div(modulus).unwrap_or(0);
let twiddle_factors = compute_twiddle_factors(degree, modulus, root_of_unity);
let device = input.device();
let shader = device.compile_shader(include_str!("../fhe_ntt.wgsl"), Some("FHE NTT Shader"));
let bind_group_layout =
device
.device
.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor {
label: Some("FHE NTT Bind Group Layout"),
entries: &[
wgpu::BindGroupLayoutEntry {
binding: 0,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: true },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 1,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: false },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 2,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: true },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 3,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Uniform,
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
],
});
let pipeline_layout =
device
.device
.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
label: Some("FHE NTT Pipeline Layout"),
bind_group_layouts: &[&bind_group_layout],
immediate_size: 0,
});
let pipeline_butterfly =
device
.device
.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
label: Some("FHE NTT Butterfly Pipeline"),
layout: Some(&pipeline_layout),
module: &shader,
entry_point: Some("main"),
cache: None,
compilation_options: Default::default(),
});
let pipeline_bit_reverse =
device
.device
.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
label: Some("FHE NTT Bit Reverse Pipeline"),
layout: Some(&pipeline_layout),
module: &shader,
entry_point: Some("bit_reverse"),
cache: None,
compilation_options: Default::default(),
});
Ok(Self {
input,
degree,
modulus,
root_of_unity,
barrett_mu,
twiddle_factors,
pipeline_butterfly,
pipeline_bit_reverse,
bind_group_layout,
})
}
pub(super) fn input(&self) -> &Tensor {
&self.input
}
pub(super) fn degree(&self) -> u32 {
self.degree
}
pub(super) fn modulus(&self) -> u64 {
self.modulus
}
pub(super) fn root_of_unity(&self) -> u64 {
self.root_of_unity
}
pub(super) fn barrett_mu(&self) -> u64 {
self.barrett_mu
}
pub(super) fn twiddle_factors(&self) -> &[u64] {
&self.twiddle_factors
}
pub(super) fn pipeline_butterfly(&self) -> &wgpu::ComputePipeline {
&self.pipeline_butterfly
}
pub(super) fn pipeline_bit_reverse(&self) -> &wgpu::ComputePipeline {
&self.pipeline_bit_reverse
}
pub(super) fn bind_group_layout(&self) -> &wgpu::BindGroupLayout {
&self.bind_group_layout
}
}
pub(crate) fn compute_twiddle_factors(degree: u32, modulus: u64, root: u64) -> Vec<u64> {
let mut factors = Vec::with_capacity(degree as usize);
let mut power = 1u64;
for _ in 0..degree {
factors.push(power);
power = (power as u128 * root as u128 % modulus as u128) as u64;
}
factors
}
fn mod_pow(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
if modulus == 1 {
return 0;
}
let mut result = 1u64;
base %= modulus;
while exp > 0 {
if exp % 2 == 1 {
result = (result as u128 * base as u128 % modulus as u128) as u64;
}
exp /= 2;
base = (base as u128 * base as u128 % modulus as u128) as u64;
}
result
}
#[must_use]
pub fn compute_primitive_root(degree: u32, modulus: u64) -> u64 {
let n = degree as u64;
if modulus < 2 || n == 0 {
return 1;
}
let q_minus_1 = modulus - 1;
if !q_minus_1.is_multiple_of(n) {
return 3; }
let exponent = q_minus_1 / n;
for &g in &[2u64, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31] {
if g >= modulus {
continue;
}
let omega = mod_pow(g, exponent, modulus);
if omega == 1 {
continue;
}
if mod_pow(omega, n, modulus) != 1 {
continue;
}
if n > 1 && n.is_multiple_of(2) && mod_pow(omega, n / 2, modulus) == 1 {
continue;
}
return omega;
}
3 }