Struct SmallConvolveGoldilocks

pub struct SmallConvolveGoldilocks;

Instantiate convolution for “small” RHS vectors over Goldilocks.

Here “small” means N = len(rhs) <= 16 and sum(r for r in rhs) < 2^51, though in practice the sum will be less than 2^9.

Trait Implementations

impl Convolve<Goldilocks, i128, i64, i128> for SmallConvolveGoldilocks

fn read(input: Goldilocks) -> i128

Return the lift of a Goldilocks element, 0 <= input.value <= P < 2^64. We widen immediately, since some valid Goldilocks elements don’t fit in an i64, and since in any case overflow can occur for even the smallest convolutions.

fn parity_dot<const N: usize>(u: [i128; N], v: [i64; N]) -> i128

For a convolution of size N, |x| < N * 2^64 and (as per the assumption above), |y| < 2^51. So the product is at most N * 2^115 which will not overflow for N <= 16. We widen y at this point to perform the multiplication.

fn reduce(z: i128) -> Goldilocks

The assumptions above mean z < N^2 * 2^115, which is at most 2^123 when N <= 16.

NB: Even though intermediate values could be negative, the output must be non-negative since the inputs were non-negative.

fn apply<const N: usize, C>(lhs: [F; N], rhs: [U; N], conv: C) -> [F; N]

where C: Fn([T; N], [U; N], &mut [V]),

Convolve lhs and rhs.

fn conv3(lhs: [T; 3], rhs: [U; 3], output: &mut [V])

fn negacyclic_conv3(lhs: [T; 3], rhs: [U; 3], output: &mut [V])

fn conv4(lhs: [T; 4], rhs: [U; 4], output: &mut [V])

fn negacyclic_conv4(lhs: [T; 4], rhs: [U; 4], output: &mut [V])

fn conv6(lhs: [T; 6], rhs: [U; 6], output: &mut [V])

fn negacyclic_conv6(lhs: [T; 6], rhs: [U; 6], output: &mut [V])

fn conv8(lhs: [T; 8], rhs: [U; 8], output: &mut [V])

fn negacyclic_conv8(lhs: [T; 8], rhs: [U; 8], output: &mut [V])

fn conv12(lhs: [T; 12], rhs: [U; 12], output: &mut [V])

fn negacyclic_conv12(lhs: [T; 12], rhs: [U; 12], output: &mut [V])

fn conv16(lhs: [T; 16], rhs: [U; 16], output: &mut [V])

fn negacyclic_conv16(lhs: [T; 16], rhs: [U; 16], output: &mut [V])

fn conv24(lhs: [T; 24], rhs: [U; 24], output: &mut [V])

fn conv32(lhs: [T; 32], rhs: [U; 32], output: &mut [V])

fn negacyclic_conv32(lhs: [T; 32], rhs: [U; 32], output: &mut [V])

fn conv64(lhs: [T; 64], rhs: [U; 64], output: &mut [V])

impl Debug for SmallConvolveGoldilocks

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.