Module libbgs::numbers

Types and utilities for manipulating numbers in various types of finite fields.

This module contains modular integers (i.e., $\mathbb{Z} / p\mathbb{Z}$ for prime $p$), their quadratic finite field extensions (i.e., $\mathbb{Z} / p^2\mathbb{Z}$ for prime $p$), and decompositions into direct sums of Sylow subgroups.

Modules

• tests
  Utility methods for use in other tests. These methods should probably not be used outside of this crate.

Macros

• impl_factors
  When called with phantom type marker Ph and a list of integers, each integer P is turned into an implementation of Factor<Ph> for FpNum<P> and Factor<Ph> for QuadNum<P>.
• lit_to_ident
• make_factor
• primes

Structs

• FactorTrie
  A trie of prime factors in increasing order; that is, a none with word $p$ will have only children with word $q \geq p$.
• Factorization
  A prime power decomposition of a positive integer.
• FpNum
  An integer modulo P.
• QuadNum
  An integer modulo P^2. An element $x$ is represented as $x = a_0 + a_1\sqrt{r}$, where $r$ is the fixed basis element. See Lubeck, Frank. (2003). “Standard generators of finite fields and their cyclic subgroups.” Journal of Symbolic Computation (117) 51-67. Note that the SylowDecomposable implementation for a QuadNum returns the decomposition for the subgroup with $p + 1$ elements, not the full group $\mathbb{F}_{p^2}^\times$. Also, <QuadNum<P> as GroupElem>::SIZE == P + 1, again refering to the subgroup. For these reasons, this API is likely to change in the future to bring the definitions of QuadNum<P> as GroupElem and the SylowDecomp instance in line with describing the full group.
• SylowDecomp
  A decomposition of a finite cyclic group into the direct sum of its Sylow subgroups. In particular, this group represents the right hand side of the isomorphism $$G \cong \bigoplus_{i = 1}^n \mathbb{Z} / p_i^{t_i} \mathbb{Z}$$ where $$|G| = \prod_{i = 1}^n p_i^{t_i}$$ and $G$ is a finite cyclic group.
• SylowElem
  An element of the decomposition of a finite cyclic group into the direct sum of its Sylow subgroups.

Traits

• Factor
  Types that have a size or order which can be expressed as a product of prime powers. The type parameter S is a phantom type to allow users of this library to provide their own factorizations for FpNum<P>, QuadNum<P>, etc. for arbitrary P. The type S must come from the crate implementing the factorization to satisfy Rust’s coherence and orphan rules, but does not affect the memory layout of any instance of an object implementing Factor. See the Rust documentation on coherence and the orphan rule.
• GroupElem
  Types that represent the elements of a group. In order for a type to represent the elements of the group, the type must satisfy these axioms:
• Length
  A placeholder trait for storing the length of a prime factorization; required to be separate from the Factor trait in order for the trait solver to avoid cycles.
• SylowDecomposable
  Groups that can be decomposed into a direct sum of cyclic Sylow subgroups. In particular, these groups must be finite and cyclic.