Struct HypercubeStructure

pub struct HypercubeStructure { /* private fields */ }

Represents a hypercube, which is a map

  h: { 0, ..., m1 - 1 } x ... x { 0, ..., mr - 1 } -> (Z/nZ)^*
                     a1,  ...,  ar                 -> prod_i gi^ai

such that the composition (mod <p>) ∘ h is a bijection.

We use the following notation:

• n and p as above
• d is the order of <p> as subgroup of (Z/nZ)*
• mi is the length of the i-th “hypercube dimension” as above
• gi is the generator of the i-th hypercube dimension

Implementations

impl HypercubeStructure

pub fn new( galois_group: CyclotomicGaloisGroup, p: CyclotomicGaloisGroupEl, d: usize, ms: Vec<usize>, gs: Vec<CyclotomicGaloisGroupEl>, ) -> Self

pub fn halevi_shoup_hypercube( galois_group: CyclotomicGaloisGroup, p: i64, ) -> Self

Computes “the” Halevi-Shoup hypercube as described in https://ia.cr/2014/873.

Note that the Halevi-Shoup hypercube is unique except for the ordering of prime factors of n. This function uses a deterministic but unspecified ordering.

pub fn map_1d(&self, dim_idx: usize, steps: i64) -> CyclotomicGaloisGroupEl

Applies the hypercube structure map to the unit vector multiple steps * e_(dim_idx), i.e. computes the galois automorphism corresponding to the shift by steps steps along the dim_idx-th hypercube dimension.

pub fn map(&self, idxs: &[i64]) -> CyclotomicGaloisGroupEl

Applies the hypercube structure map to the given vector.

It is not enforced that the entries of the vector are contained in { 0, ..., m1 - 1 } x ... x { 0, ..., mr - 1 }, for values outside this range the natural extension of h to Z^r is used, i.e.

  h:       Z^r      ->   (Z/nZ)^*
     a1,  ...,  ar  -> prod_i gi^ai

pub fn map_usize(&self, idxs: &[usize]) -> CyclotomicGaloisGroupEl

Same as HypercubeStructure::map(), but for a vector with unsigned entries.

pub fn std_preimage(&self, g: CyclotomicGaloisGroupEl) -> &[usize]

Computes the “standard preimage” of the given g under h.

This is the vector (a0, a1, ..., ar) such that g = p^a0 h(a1, ..., ar) and each ai is within { 0, ..., mi - 1 }.

pub fn is_tensor_product_compatible(&self) -> bool

Returns whether each dimension of the hypercube corresponds to a factor ni of n (with ni coprime to n/ni). This is the case for the Halevi-Shoup hypercube, and very useful in some situations. If this is the case, you can query the factor of n corresponding to some dimension by HypercubeStructure::factor_of_n().

pub fn factor_of_n(&self, dim_idx: usize) -> Option<i64>

Returns the factor ni of n (coprime to n/ni) which the i-th hypercube dimension corresponds to. This is only applicable if the hypercube was constructed from a (partial) factorization of n, i.e. HypercubeStructure::is_tensor_product_compatible() returns true. Otherwise, this function will return None.

pub fn p(&self) -> CyclotomicGaloisGroupEl

Returns p as an element of (Z/nZ)*.

pub fn frobenius(&self, power: i64) -> CyclotomicGaloisGroupEl

Returns the Galois automorphism corresponding to the power-of-p^power frobenius automorphism of the slot ring.

pub fn d(&self) -> usize

Returns the rank d of the slot ring.

pub fn m(&self, i: usize) -> usize

Returns the length mi of the i-th hypercube dimension.

pub fn g(&self, i: usize) -> CyclotomicGaloisGroupEl

Returns the generator gi corresponding to the i-th hypercube dimension.

pub fn ord_g(&self, i: usize) -> usize

Returns the order of gi in the group (Z/nZ)*.

pub fn n(&self) -> usize

Returns n, i.e. the multiplicative order of the root of unity of the main ring.

pub fn dim_count(&self) -> usize

Returns the number of dimensions in the hypercube.

pub fn galois_group(&self) -> &CyclotomicGaloisGroup

Returns the Galois group isomorphic to (Z/nZ)* that this hypercube describes.

pub fn element_count(&self) -> usize

Returns the number of elements of { 0, ..., m1 - 1 } x ... x { 0, ..., mr - 1 } or equivalently (Z/nZ)*/<p>, which is equal to the to the number of slots of Fp[X]/(Phi_n(X)).

pub fn hypercube_iter<'b, G, T>( &'b self, for_slot: G, ) -> impl ExactSizeIterator<Item = T> + use<'b, G, T>

where G: 'b + Clone + FnMut(&[usize]) -> T, T: 'b,

Creates an iterator that yields a value for each element of { 0, ..., m1 - 1 } x ... x { 0, ..., mr - 1 } resp. (Z/nZ)*/<p>. Hence, these elements correspond to the slots of Fp[X]/(Phi_n(X)).

The given closure will be called on each element of { 0, ..., m1 - 1 } x ... x { 0, ..., mr - 1 }. The returned iterator will iterate over the results of the closure.

pub fn element_iter<'b>( &'b self, ) -> impl ExactSizeIterator<Item = CyclotomicGaloisGroupEl> + use<'b>

Creates an iterator that one representative of each element of (Z/nZ)*/<p>, which also is in the image of this hypercube structure.

The order is compatible with HypercubeStructure::hypercube_iter().

Trait Implementations

impl Clone for HypercubeStructure

fn clone(&self) -> HypercubeStructure

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'de> Deserialize<'de> for HypercubeStructure

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl PartialEq for HypercubeStructure

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for HypercubeStructure

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.