use super::config::{NttConfig, NttRepresentation, power_mod};
use crate::{
DType, Engine, Error, Matrix, OpAttribute, Result,
runtime::{BufferBinding, ComputeDispatch, KernelId, PushConstant, SemanticDispatch},
};
#[derive(Clone)]
pub struct NttParameters {
config: NttConfig,
forward: Matrix,
inverse: Matrix,
negative_inverse: u32,
r2: u64,
inverse_length: u64,
}
impl NttParameters {
pub const fn config(&self) -> &NttConfig {
&self.config
}
}
pub fn prepare(engine: &Engine, config: &NttConfig) -> Result<NttParameters> {
let engine = engine.handle();
let modulus = config.modulus;
let root = config.root;
let one = ((1_u128 << 64) % u128::from(modulus)) as u64;
let r2 = ((u128::from(one) * u128::from(one)) % u128::from(modulus)) as u64;
let root_montgomery = ((u128::from(root) * u128::from(one)) % u128::from(modulus)) as u64;
let inverse_root = power_mod(root, modulus - 2, modulus);
let inverse_root_montgomery =
((u128::from(inverse_root) * u128::from(one)) % u128::from(modulus)) as u64;
let inverse_length = ((u128::from(power_mod(config.length as u64, modulus - 2, modulus))
* u128::from(one))
% u128::from(modulus)) as u64;
let mut inverse = 1_u32;
for _ in 0..5 {
inverse = inverse.wrapping_mul(2_u32.wrapping_sub((modulus as u32).wrapping_mul(inverse)));
}
let negative_inverse = inverse.wrapping_neg();
let count = (config.length / 2) as u32;
let groups = engine.linear_dispatch_grid(count, 128)?;
let forward = Matrix::allocate_output(
&engine,
vec![config.length / 2, 2],
config.length,
DType::U32,
)?;
let inverse = Matrix::allocate_output(
&engine,
vec![config.length / 2, 2],
config.length,
DType::U32,
)?;
let kernel = KernelId::CryptographyNttTwiddlesU32;
let buffers = [
BufferBinding::write(forward.storage()),
BufferBinding::write(inverse.storage()),
];
let push_constants = [
PushConstant::U32(count),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(modulus as u32),
PushConstant::U32((modulus >> 32) as u32),
PushConstant::U32(negative_inverse),
PushConstant::U32(root_montgomery as u32),
PushConstant::U32((root_montgomery >> 32) as u32),
PushConstant::U32(inverse_root_montgomery as u32),
PushConstant::U32((inverse_root_montgomery >> 32) as u32),
PushConstant::U32(one as u32),
PushConstant::U32((one >> 32) as u32),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "modulus".into(),
value: modulus,
},
OpAttribute::UnsignedInteger {
name: "length".into(),
value: config.length as u64,
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::ntt::NTT_TWIDDLES,
inputs: &[],
outputs: &[&forward, &inverse],
attributes: &attributes,
},
)?;
Ok(NttParameters {
config: config.clone(),
forward,
inverse,
negative_inverse,
r2,
inverse_length,
})
}
pub fn forward(input: &Matrix, parameters: &NttParameters) -> Result<Matrix> {
let config = ¶meters.config;
if input.dtype() != DType::U32
|| input.shape().len() != 3
|| input.shape()[1..] != [config.length, 2]
|| !input
.engine_handle()
.same_as(parameters.forward.engine_handle())
{
return Err(Error::invalid_argument(
"NTT requires matching-owner U32 [batch, length, 2] coefficients",
));
}
let elements = input.num_elements();
let bytes = elements
.checked_mul(4)
.ok_or_else(|| Error::invalid_argument("NTT input byte extent overflows usize"))?;
u32::try_from(bytes).map_err(|_| Error::invalid_argument("NTT input byte extent exceeds u32"))?;
let count = u32::try_from(elements / 2)
.map_err(|_| Error::invalid_argument("NTT coefficient count exceeds u32"))?;
let engine = input.engine_handle();
let first = Matrix::allocate_output(engine, input.shape().to_vec(), elements, DType::U32)?;
if count == 0 {
return Ok(first);
}
let twiddles = ¶meters.forward;
let modulus = config.modulus;
let montgomery = u32::from(config.representation == NttRepresentation::Montgomery);
let normalization = ((1_u128 << 64) % u128::from(modulus)) as u64;
let shared_bytes = engine.compute_shared_memory_bytes() as usize;
let cooperative = [
(256, KernelId::CryptographyNttCooperative256U32),
(1024, KernelId::CryptographyNttCooperative1024U32),
(4096, KernelId::CryptographyNttCooperative4096U32),
(8192, KernelId::CryptographyNttCooperative8192U32),
]
.into_iter()
.find(|(capacity, _)| config.length <= *capacity && capacity * 8 <= shared_bytes);
if let Some((_, kernel)) = cooperative {
let groups = engine.linear_dispatch_grid(input.shape()[0] as u32, 1)?;
let buffers = [
BufferBinding::read(input.storage()),
BufferBinding::read(twiddles.storage()),
BufferBinding::write(first.storage()),
];
let push_constants = [
PushConstant::U32(input.shape()[0] as u32),
PushConstant::U32(groups[0]),
PushConstant::U32(config.length as u32),
PushConstant::U32(config.length.trailing_zeros()),
PushConstant::U32(modulus as u32),
PushConstant::U32((modulus >> 32) as u32),
PushConstant::U32(parameters.negative_inverse),
PushConstant::U32(parameters.r2 as u32),
PushConstant::U32((parameters.r2 >> 32) as u32),
PushConstant::U32(normalization as u32),
PushConstant::U32((normalization >> 32) as u32),
PushConstant::U32(montgomery),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "modulus".into(),
value: modulus,
},
OpAttribute::UnsignedInteger {
name: "length".into(),
value: config.length as u64,
},
OpAttribute::UnsignedInteger {
name: "inverse".into(),
value: 0,
},
OpAttribute::UnsignedInteger {
name: "montgomery".into(),
value: u64::from(montgomery),
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::ntt::NTT_TRANSFORM,
inputs: &[input, twiddles],
outputs: &[&first],
attributes: &attributes,
},
)?;
return Ok(first);
}
let second = Matrix::allocate_output(engine, input.shape().to_vec(), elements, DType::U32)?;
let groups = engine.linear_dispatch_grid(count, 128)?;
let kernel = KernelId::CryptographyNttReorderU32;
let buffers = [
BufferBinding::read(input.storage()),
BufferBinding::write(first.storage()),
];
let push_constants = [
PushConstant::U32(count),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(config.length as u32),
PushConstant::U32(config.length.trailing_zeros()),
PushConstant::U32(modulus as u32),
PushConstant::U32((modulus >> 32) as u32),
PushConstant::U32(parameters.negative_inverse),
PushConstant::U32(parameters.r2 as u32),
PushConstant::U32((parameters.r2 >> 32) as u32),
PushConstant::U32(montgomery),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "modulus".into(),
value: modulus,
},
OpAttribute::UnsignedInteger {
name: "length".into(),
value: config.length as u64,
},
OpAttribute::UnsignedInteger {
name: "montgomery".into(),
value: u64::from(montgomery),
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::ntt::NTT_REORDER,
inputs: &[input],
outputs: &[&first],
attributes: &attributes,
},
)?;
let groups = engine.linear_dispatch_grid(count / 2, 128)?;
let mut current = first.clone();
for stage in 1..=config.length.trailing_zeros() {
let span = 1_u32 << stage;
let target = if stage % 2 == 1 { &second } else { &first };
let output = target.reshape_semantic_output(input.shape().to_vec())?;
let kernel = KernelId::CryptographyNttStageU32;
let buffers = [
BufferBinding::read(current.storage()),
BufferBinding::read(twiddles.storage()),
BufferBinding::write(output.storage()),
];
let push_constants = [
PushConstant::U32(count / 2),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(config.length as u32),
PushConstant::U32(span),
PushConstant::U32(modulus as u32),
PushConstant::U32((modulus >> 32) as u32),
PushConstant::U32(parameters.negative_inverse),
PushConstant::U32(normalization as u32),
PushConstant::U32((normalization >> 32) as u32),
PushConstant::U32(montgomery),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "modulus".into(),
value: modulus,
},
OpAttribute::UnsignedInteger {
name: "length".into(),
value: config.length as u64,
},
OpAttribute::UnsignedInteger {
name: "span".into(),
value: u64::from(span),
},
OpAttribute::UnsignedInteger {
name: "inverse".into(),
value: 0,
},
OpAttribute::UnsignedInteger {
name: "montgomery".into(),
value: u64::from(montgomery),
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::ntt::NTT_STAGE,
inputs: &[¤t, twiddles],
outputs: &[&output],
attributes: &attributes,
},
)?;
current = output;
}
Ok(current)
}
pub fn inverse(input: &Matrix, parameters: &NttParameters) -> Result<Matrix> {
let config = ¶meters.config;
if input.dtype() != DType::U32
|| input.shape().len() != 3
|| input.shape()[1..] != [config.length, 2]
|| !input
.engine_handle()
.same_as(parameters.forward.engine_handle())
{
return Err(Error::invalid_argument(
"NTT requires matching-owner U32 [batch, length, 2] coefficients",
));
}
let elements = input.num_elements();
let bytes = elements
.checked_mul(4)
.ok_or_else(|| Error::invalid_argument("NTT input byte extent overflows usize"))?;
u32::try_from(bytes).map_err(|_| Error::invalid_argument("NTT input byte extent exceeds u32"))?;
let count = u32::try_from(elements / 2)
.map_err(|_| Error::invalid_argument("NTT coefficient count exceeds u32"))?;
let engine = input.engine_handle();
let first = Matrix::allocate_output(engine, input.shape().to_vec(), elements, DType::U32)?;
if count == 0 {
return Ok(first);
}
let twiddles = ¶meters.inverse;
let modulus = config.modulus;
let montgomery = u32::from(config.representation == NttRepresentation::Montgomery);
let normalization = parameters.inverse_length;
let shared_bytes = engine.compute_shared_memory_bytes() as usize;
let cooperative = [
(256, KernelId::CryptographyNttCooperative256U32),
(1024, KernelId::CryptographyNttCooperative1024U32),
(4096, KernelId::CryptographyNttCooperative4096U32),
(8192, KernelId::CryptographyNttCooperative8192U32),
]
.into_iter()
.find(|(capacity, _)| config.length <= *capacity && capacity * 8 <= shared_bytes);
if let Some((_, kernel)) = cooperative {
let groups = engine.linear_dispatch_grid(input.shape()[0] as u32, 1)?;
let buffers = [
BufferBinding::read(input.storage()),
BufferBinding::read(twiddles.storage()),
BufferBinding::write(first.storage()),
];
let push_constants = [
PushConstant::U32(input.shape()[0] as u32),
PushConstant::U32(groups[0]),
PushConstant::U32(config.length as u32),
PushConstant::U32(config.length.trailing_zeros()),
PushConstant::U32(modulus as u32),
PushConstant::U32((modulus >> 32) as u32),
PushConstant::U32(parameters.negative_inverse),
PushConstant::U32(parameters.r2 as u32),
PushConstant::U32((parameters.r2 >> 32) as u32),
PushConstant::U32(normalization as u32),
PushConstant::U32((normalization >> 32) as u32),
PushConstant::U32(montgomery),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "modulus".into(),
value: modulus,
},
OpAttribute::UnsignedInteger {
name: "length".into(),
value: config.length as u64,
},
OpAttribute::UnsignedInteger {
name: "inverse".into(),
value: 1,
},
OpAttribute::UnsignedInteger {
name: "montgomery".into(),
value: u64::from(montgomery),
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::ntt::NTT_TRANSFORM,
inputs: &[input, twiddles],
outputs: &[&first],
attributes: &attributes,
},
)?;
return Ok(first);
}
let second = Matrix::allocate_output(engine, input.shape().to_vec(), elements, DType::U32)?;
let groups = engine.linear_dispatch_grid(count, 128)?;
let kernel = KernelId::CryptographyNttReorderU32;
let buffers = [
BufferBinding::read(input.storage()),
BufferBinding::write(first.storage()),
];
let push_constants = [
PushConstant::U32(count),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(config.length as u32),
PushConstant::U32(config.length.trailing_zeros()),
PushConstant::U32(modulus as u32),
PushConstant::U32((modulus >> 32) as u32),
PushConstant::U32(parameters.negative_inverse),
PushConstant::U32(parameters.r2 as u32),
PushConstant::U32((parameters.r2 >> 32) as u32),
PushConstant::U32(montgomery),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "modulus".into(),
value: modulus,
},
OpAttribute::UnsignedInteger {
name: "length".into(),
value: config.length as u64,
},
OpAttribute::UnsignedInteger {
name: "montgomery".into(),
value: u64::from(montgomery),
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::ntt::NTT_REORDER,
inputs: &[input],
outputs: &[&first],
attributes: &attributes,
},
)?;
let groups = engine.linear_dispatch_grid(count / 2, 128)?;
let mut current = first.clone();
for stage in 1..=config.length.trailing_zeros() {
let span = 1_u32 << stage;
let target = if stage % 2 == 1 { &second } else { &first };
let output = target.reshape_semantic_output(input.shape().to_vec())?;
let kernel = KernelId::CryptographyNttStageU32;
let buffers = [
BufferBinding::read(current.storage()),
BufferBinding::read(twiddles.storage()),
BufferBinding::write(output.storage()),
];
let push_constants = [
PushConstant::U32(count / 2),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(config.length as u32),
PushConstant::U32(span),
PushConstant::U32(modulus as u32),
PushConstant::U32((modulus >> 32) as u32),
PushConstant::U32(parameters.negative_inverse),
PushConstant::U32(normalization as u32),
PushConstant::U32((normalization >> 32) as u32),
PushConstant::U32(montgomery),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "modulus".into(),
value: modulus,
},
OpAttribute::UnsignedInteger {
name: "length".into(),
value: config.length as u64,
},
OpAttribute::UnsignedInteger {
name: "span".into(),
value: u64::from(span),
},
OpAttribute::UnsignedInteger {
name: "inverse".into(),
value: 1,
},
OpAttribute::UnsignedInteger {
name: "montgomery".into(),
value: u64::from(montgomery),
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::ntt::NTT_STAGE,
inputs: &[¤t, twiddles],
outputs: &[&output],
attributes: &attributes,
},
)?;
current = output;
}
Ok(current)
}
pub fn pointwise_multiply(
left: &Matrix,
right: &Matrix,
parameters: &NttParameters,
) -> Result<Matrix> {
let config = ¶meters.config;
if left.dtype() != DType::U32
|| left.shape().len() != 3
|| left.shape()[1..] != [config.length, 2]
|| right.dtype() != DType::U32
|| right.shape() != left.shape()
|| !left.engine_handle().same_as(right.engine_handle())
|| !left
.engine_handle()
.same_as(parameters.forward.engine_handle())
{
return Err(Error::invalid_argument(
"NTT pointwise multiplication requires matching-owner U32 [batch, length, 2] rows",
));
}
let elements = left.num_elements();
let bytes = elements
.checked_mul(4)
.ok_or_else(|| Error::invalid_argument("NTT byte extent overflows usize"))?;
u32::try_from(bytes).map_err(|_| Error::invalid_argument("NTT byte extent exceeds u32"))?;
let count = u32::try_from(elements / 2)
.map_err(|_| Error::invalid_argument("NTT coefficient count exceeds u32"))?;
let engine = left.engine_handle();
let output = Matrix::allocate_output(engine, left.shape().to_vec(), elements, DType::U32)?;
if count != 0 {
let groups = engine.linear_dispatch_grid(count, 128)?;
let kernel = KernelId::CryptographyNttPointwiseU32;
let buffers = [
BufferBinding::read(left.storage()),
BufferBinding::read(right.storage()),
BufferBinding::write(output.storage()),
];
let push_constants = [
PushConstant::U32(count),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(config.modulus as u32),
PushConstant::U32((config.modulus >> 32) as u32),
PushConstant::U32(parameters.negative_inverse),
PushConstant::U32(parameters.r2 as u32),
PushConstant::U32((parameters.r2 >> 32) as u32),
PushConstant::U32(u32::from(
config.representation == NttRepresentation::Montgomery,
)),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "modulus".into(),
value: config.modulus,
},
OpAttribute::UnsignedInteger {
name: "length".into(),
value: config.length as u64,
},
OpAttribute::UnsignedInteger {
name: "montgomery".into(),
value: u64::from(config.representation == NttRepresentation::Montgomery),
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::ntt::NTT_POINTWISE,
inputs: &[left, right],
outputs: &[&output],
attributes: &attributes,
},
)?;
}
Ok(output)
}