Trait quack::PowerSumQuack

source ·

pub trait PowerSumQuack {
    type Element;
    type ModularElement;

    // Required methods
    fn new(threshold: usize) -> Self
       where Self: Sized;
    fn threshold(&self) -> usize;
    fn count(&self) -> u32;
    fn last_value(&self) -> Option<Self::Element>;
    fn insert(&mut self, value: Self::Element);
    fn remove(&mut self, value: Self::Element);
    fn decode_with_log(&self, log: &[Self::Element]) -> Vec<Self::Element>;
    fn to_coeffs(&self) -> CoefficientVector<Self::ModularElement>;
    fn to_coeffs_preallocated(
        &self,
        coeffs: &mut CoefficientVector<Self::ModularElement>
    );
    fn sub_assign(&mut self, rhs: Self);
    fn sub(self, rhs: Self) -> Self;
}

Expand description

A quACK represented by a threshold number of power sums.

The power sum quACK is useful for decoding a set difference of elements when the number of elements in the set difference is comparatively small to the number of elements in either set. It is also efficient to insert elements in the power sum quACK. The tradeoff is that it becomes impossible to decode the quACK when the number of elements in the quACK exceeds a pre-determined threshold. The number of bytes needed to transmit the quACK over the wire is proportional to this threshold.

The underlying representation of a power sum quACK is a threshold number of power sums. If X is the multiset of elements in the quACK, then the i-th power sum is just the sum of x^i for all x in X.

Required Associated Types§

source

type Element

The type of element that can be inserted in the quACK.

source

type ModularElement

The modular version of the elements in the quACK.

Required Methods§

source

fn new(threshold: usize) -> Selfwhere Self: Sized,

Creates a new power sum quACK that can decode at most threshold number of elements.

source

fn threshold(&self) -> usize

The maximum number of elements that can be decoded by the quACK.

source

fn count(&self) -> u32

The number of elements represented by the quACK.

source

fn last_value(&self) -> Option<Self::Element>

The last element inserted in the quACK, if known.

If None, either there are no elements in the quACK, or a previous last element was removed and the actual last element is unknown.

source

fn insert(&mut self, value: Self::Element)

Insert an element in the quACK.

source

fn remove(&mut self, value: Self::Element)

Remove an element in the quACK. Does not validate that the element had actually been inserted in the quACK.

source

fn decode_with_log(&self, log: &[Self::Element]) -> Vec<Self::Element>

Decode the elements in the log that in the quACK.

This method evaluates the polynomial derived from the power sums in the quACK at each of the candidate roots in the log, returning the roots. If a root appears more than once in the log, it will appear the same number of times in the returned roots. Note that the decoding method does not consider the root multiplicity in the polynomial. If the log is incomplete, there will be fewer roots returned than the actual number of elements represented by the quACK.

source

fn to_coeffs(&self) -> CoefficientVector<Self::ModularElement>

Convert the n modular power sums that represent the elements in the quACK to a degree-n polynomial in the same field. The polynomial is represented by a vector of coefficients, and the coefficients are calculated using Newton’s identities.

Examples

use quack::{PowerSumQuack, PowerSumQuackU32};
use quack::arithmetic::{ModularInteger, ModularArithmetic};

const THRESHOLD: usize = 20;
const ROOT1: u32 = 10;
const ROOT2: u32 = 12;

fn main() {
    // Polynomial with degree 1
    let mut quack = PowerSumQuackU32::new(THRESHOLD);
    quack.insert(ROOT1);
    let coeffs = quack.to_coeffs();  // x - 10
    assert_eq!(coeffs.len(), 1);
    assert_eq!(coeffs, vec![ModularInteger::<u32>::new(ROOT1).neg()]);

    // Polynomial with degree 2
    quack.insert(ROOT2);
    let coeffs = quack.to_coeffs();  // x^2 - 24x + 120
    let mut quack1 = PowerSumQuackU32::new(THRESHOLD);
    assert_eq!(coeffs.len(), 2);
    assert_eq!(coeffs, vec![
        ModularInteger::<u32>::new(ROOT1 + ROOT2).neg(),
        ModularInteger::<u32>::new(ROOT1 * ROOT2),
    ]);
}

source

fn to_coeffs_preallocated( &self, coeffs: &mut CoefficientVector<Self::ModularElement> )

Similar to to_coeffs but reuses the same vector allocation to return the coefficients.

source

fn sub_assign(&mut self, rhs: Self)

Subtracts another power sum quACK from this power sum quACK.

The difference between a quACK with x elements and a quACK with y elements is a quACK with x - y elements. Assumes the elements in the second quACK are a subset of the elements in the first quACK. Assumes the two quACKs have the same threshold. If these conditions are met, then the x - y elements in the difference represent the set difference, and can be decoded from the quACK as long as this number of elements does not exceed the threshold.

Examples

use quack::{PowerSumQuack, PowerSumQuackU32};
use quack::arithmetic::{ModularInteger, ModularArithmetic};

const THRESHOLD: usize = 20;

fn main() {
    // Insert some elements in the first quACK.
    let mut quack1 = PowerSumQuackU32::new(THRESHOLD);
    quack1.insert(1);
    quack1.insert(2);
    quack1.insert(3);
    quack1.insert(4);
    quack1.insert(5);

    // Insert a subset of the same elements in the second quACK.
    let mut quack2 = PowerSumQuackU32::new(THRESHOLD);
    quack2.insert(2);
    quack2.insert(5);

    // Subtract the second quACK from the first and decode the elements.
    quack1.sub_assign(quack2);
    let mut roots = quack1.decode_with_log(&[1, 2, 3, 4, 5]);
    roots.sort();
    assert_eq!(roots, vec![1, 3, 4]);
}