pub struct G2Poly(pub u64);
Expand description
Polynomial representation of values Main type exported by this library
The polynomial is represented as the bits of the inner u64
. The least significant bit
represents c_0
in c_n * x^n + c_(n-1) * x^(n-1) + ... + c_0 * x^0
, the next bit c_1 and so on.
assert_eq!(format!("{}", G2Poly(0b101)), "G2Poly { x^2 + 1 }");
3 main operations +
, -
and
*
are implemented, as well as %
for remainder
calculation. Note that multiplication generates a G2PolyProd
so there is no risk of
overflow.
Division is left out as there is generally not needed for common use cases. This may change in a later release.
Tuple Fields§
§0: u64
Implementations§
source§impl G2Poly
impl G2Poly
sourcepub const UNIT: G2Poly = G2Poly(1)
pub const UNIT: G2Poly = G2Poly(1)
The constant 1
polynomial.
This is the multiplicative identity. (a * UNIT = a)
sourcepub const ZERO: G2Poly = G2Poly(0)
pub const ZERO: G2Poly = G2Poly(0)
The constant 0 polynomial
This is the additive identity (a + ZERO = a)
sourcepub fn pow_mod(self, power: u64, modulus: G2Poly) -> G2Poly
pub fn pow_mod(self, power: u64, modulus: G2Poly) -> G2Poly
Quickly calculate p^n mod m
Uses square-and-multiply to quickly exponentiate a polynomial.
Example
let p = G2Poly(0b1011);
assert_eq!(p.pow_mod(127, G2Poly(0b1101)), G2Poly(0b110));
sourcepub fn is_irreducible(self) -> bool
pub fn is_irreducible(self) -> bool
Determine if the given polynomial is irreducible.
Irreducible polynomials not be expressed as the product of other irreducible polynomials
(except 1
and itself). This uses Rabin’s tests
to check if the given polynomial is irreducible.
Example
let p = G2Poly(0b101);
assert!(!p.is_irreducible()); // x^2 + 1 == (x + 1)^2 in GF(2)
let p = G2Poly(0b111);
assert!(p.is_irreducible());
sourcepub fn degree(self) -> Option<u64>
pub fn degree(self) -> Option<u64>
Get the degree of the polynomial
Returns None
for the 0 polynomial (which has degree -infinity
),
otherwise is guaranteed to return Some(d)
with d
the degree.
let z = G2Poly::ZERO;
assert_eq!(z.degree(), None);
let s = G2Poly(0b101);
assert_eq!(s.degree(), Some(2));
sourcepub fn is_generator(self, module: G2Poly) -> bool
pub fn is_generator(self, module: G2Poly) -> bool
Checks if a polynomial generates the multiplicative group mod m.
The field GF(2^p) can be interpreted as all polynomials of degree < p, with all operations
carried over from polynomials. Multiplication is done mod m, where m is some irreducible
polynomial of degree p. The multiplicative group is cyclic, so there is an element a
so
that all elements != can be expressed as a^n for some n < 2^p - 1.
This checks if the given polynomial is such a generator element mod m.
Example
let m = G2Poly(0b10011101);
// The element `x` generates the whole group.
assert!(G2Poly::X.is_generator(m));
Trait Implementations§
source§impl Div<G2Poly> for G2Poly
impl Div<G2Poly> for G2Poly
source§impl Mul<G2Poly> for G2Poly
impl Mul<G2Poly> for G2Poly
§type Output = G2PolyProd
type Output = G2PolyProd
*
operator.source§impl Ord for G2Poly
impl Ord for G2Poly
source§impl PartialEq<G2Poly> for G2Poly
impl PartialEq<G2Poly> for G2Poly
source§impl PartialOrd<G2Poly> for G2Poly
impl PartialOrd<G2Poly> for G2Poly
1.0.0 · source§fn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
self
and other
) and is used by the <=
operator. Read more