Struct TwoAdicMultiplicativeCoset 

pub struct TwoAdicMultiplicativeCoset<F: TwoAdicField> { /* private fields */ }

Coset of a subgroup of the group of units of a finite field of order equal to a power of two.

Examples

    TwoAdicField,
    PrimeCharacteristicRing,
    coset::TwoAdicMultiplicativeCoset
};
type F = BabyBear;
let log_size = 3;
let shift = F::from_u64(7);
let mut coset = TwoAdicMultiplicativeCoset::new(shift, log_size).unwrap();
let generator = coset.subgroup_generator();

// Coset elements can be queried by index
assert_eq!(coset.element(4), shift * generator.exp_u64(4));

// Coset elements can be iterated over in the canonical order
assert_eq!(
    coset.iter().collect_vec(),
    (0..1 << log_size).map(|i| shift * generator.exp_u64(i)).collect_vec()
);

// Cosets can be (element-wise) raised to a power of 2, either maintaining
// the shift and raising only the subgroup, or raising both.
let coset_shrunk_subgroup = coset.shrink_coset(2).unwrap();
assert_eq!(
    coset_shrunk_subgroup.subgroup_generator(),
    coset.subgroup_generator().exp_power_of_2(2),
);
assert_eq!(
    coset_shrunk_subgroup.shift(),
    coset.shift()
);

let coset_power = coset.exp_power_of_2(2).unwrap();
assert_eq!(
    coset_power.subgroup_generator(),
    coset.subgroup_generator().exp_power_of_2(2),
);
assert_eq!(
    coset_power.shift(),
    coset.shift().exp_power_of_2(2),
);

Implementations

impl<F: TwoAdicField> TwoAdicMultiplicativeCoset<F>

pub fn new(shift: F, log_size: usize) -> Option<Self>

Returns the coset shift * <generator>, where generator is a canonical (i. e. fixed in the implementation of F: TwoAdicField) generator of the unique subgroup of the units of F of order 2 ^ log_size. Returns None if log_size > F::TWO_ADICITY or if shift is zero.

Arguments

• shift: the value by which the subgroup is (multiplicatively) shifted
• log_size: the size of the subgroup (and hence of the coset) is 2 ^ log_size. This determines the subgroup uniquely.

pub fn subgroup_generator(&self) -> F

Returns the generator of the subgroup of order self.size().

pub const fn shift(&self) -> F

Returns the shift of the coset.

pub const fn shift_inverse(&self) -> F

Returns the inverse of the coset shift.

pub const fn log_size(&self) -> usize

Returns the log2 of the size of the coset.

pub const fn size(&self) -> usize

Returns the size of the coset.

pub fn shrink_coset(&self, log_scale_factor: usize) -> Option<Self>

Returns a new coset with its subgroup reduced by a factor of 2^log_scale_factor in size (i. e. with generator equal to the 2^log_scale_factor-th power of that of the original coset), leaving the shift untouched. Note that new coset is contained in the original one. Returns None if log_scale_factor is greater than self.log_size().

pub fn exp_power_of_2(&self, log_scale_factor: usize) -> Option<Self>

Returns the coset self^(2^log_scale_factor) (i. e. with shift and subgroup generator equal to the 2^log_scale_factor-th power of the original ones). Returns None if log_scale_factor is greater than self.log_size().

pub fn shift_by(&self, scale: F) -> Self

Returns a new coset of the same size whose shift is equal to scale * self.shift.

pub fn set_shift(&self, shift: F) -> Self

Returns a new coset where the shift has been set to shift

pub fn contains(&self, element: F) -> bool

Checks if the given field element is in the coset

pub fn element(&mut self, index: usize) -> F

Returns the element shift * generator^index, which is the index % self.size()-th element of self (and, in particular, the index-th element of self whenever index < self.size()).

pub fn iter(&self) -> Take<Powers<F>>

Returns an iterator over the elements of the coset in the canonical order shift * generator^0, shift * generator^1, ..., shift * generator^(2^log_size - 1).

Trait Implementations

impl<F: Clone + TwoAdicField> Clone for TwoAdicMultiplicativeCoset<F>

fn clone(&self) -> TwoAdicMultiplicativeCoset<F>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F: Debug + TwoAdicField> Debug for TwoAdicMultiplicativeCoset<F>

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

Formats the value using the given formatter.

impl<F: TwoAdicField> IntoIterator for &TwoAdicMultiplicativeCoset<F>

type Item = F

The type of the elements being iterated over.

type IntoIter = Take<Powers<F>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<F: TwoAdicField> IntoIterator for TwoAdicMultiplicativeCoset<F>

type Item = F

The type of the elements being iterated over.

type IntoIter = Take<Powers<F>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<F: Copy + TwoAdicField> Copy for TwoAdicMultiplicativeCoset<F>