use super::*;
use crate::field::{Fp, PrimeField};
fn product(
end: &HomotopyHomQuotient,
left: &[Fp],
right: &[Fp],
meter: &mut WorkMeter,
) -> Result<Vec<Fp>, Interrupt> {
meter.charge()?;
let map = end.representative(left).then(&end.representative(right))?;
Ok(end.reduce(&map)?.0)
}
fn power(
end: &HomotopyHomQuotient,
base: &[Fp],
mut exponent: u64,
one: &[Fp],
meter: &mut WorkMeter,
) -> Result<Vec<Fp>, Interrupt> {
let (mut result, mut base) = (one.to_vec(), base.to_vec());
while exponent > 0 {
if exponent & 1 == 1 {
result = product(end, &result, &base, meter)?;
}
exponent >>= 1;
if exponent > 0 {
base = product(end, &base, &base, meter)?;
}
}
Ok(result)
}
pub(super) fn residue_of(field: PrimeField, residue: &[Fp], coordinates: &[Fp]) -> Fp {
let terms = residue.iter().zip(coordinates);
terms.fold(field.zero(), |sum, (a, b)| {
field.add(sum, field.mul(*a, *b))
})
}
pub(super) fn local_residue(
end: &HomotopyHomQuotient,
meter: &mut WorkMeter,
) -> Result<Option<Vec<Fp>>, Interrupt> {
let field = end.source().terms()[0].field();
let dim = end.dim();
let one = end.reduce(&ChainMap::identity(end.source()))?.0;
let mut exponent = 1u64;
while (exponent as usize) < dim {
exponent = exponent.saturating_mul(field.modulus());
}
let identity_line = DenseMat::from_rows(std::slice::from_ref(&one)).transpose();
let mut residue = Vec::with_capacity(dim);
for index in 0..dim {
let mut unit = vec![field.zero(); dim];
unit[index] = field.one();
let value = power(end, &unit, exponent, &one, meter)?;
let Some(scalar) = identity_line.solve(&value, &field) else {
return Ok(None);
};
residue.push(scalar[0]);
}
if residue_of(field, &residue, &one).is_zero() {
return Ok(None);
}
let radical = DenseMat::from_rows(std::slice::from_ref(&residue)).kernel_basis(&field);
let mut ideal_power = radical.clone();
for _ in 0..dim {
let pairs = (0..ideal_power.rows())
.flat_map(|left| (0..radical.rows()).map(move |right| (left, right)));
let rows = pairs
.map(|(left, right)| product(end, ideal_power.row(left), radical.row(right), meter))
.collect::<Result<Vec<_>, _>>()?;
ideal_power = DenseMat::from_rows_with_cols(&rows, dim).row_space_basis(&field);
}
Ok((ideal_power.rows() == 0).then_some(residue))
}