Struct g2poly::G2Poly

pub struct G2Poly(pub u64);

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.

Methods

impl G2Poly

pub const UNIT: Self

The constant 1 polynomial.

This is the multiplicative identity. (a * UNIT = a)

pub const ZERO: Self

The constant 0 polynomial

This is the additive identity (a + ZERO = a)

pub const X: Self

The x polynomial.

Useful for quickly generating x^n values.

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));

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());

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));

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

impl Copy for G2Poly

impl Ord for G2Poly

fn cmp(&self, other: &G2Poly) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

🔬 This is a nightly-only experimental API. (clamp)

Restrict a value to a certain interval.

impl Clone for G2Poly

fn clone(&self) -> G2Poly

Returns a copy of the value.

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

Performs copy-assignment from source.

impl PartialEq<G2Poly> for G2Poly

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

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=.

impl PartialOrd<G2Poly> for G2Poly

fn partial_cmp(&self, other: &G2Poly) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &G2Poly) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &G2Poly) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &G2Poly) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &G2Poly) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl Eq for G2Poly

impl Debug for G2Poly

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

Formats the value using the given formatter.

impl Display for G2Poly

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

Formats the value using the given formatter.

impl Add<G2Poly> for G2Poly

type Output = G2Poly

The resulting type after applying the + operator.

fn add(self, rhs: G2Poly) -> G2Poly

Performs the + operation.

impl Sub<G2Poly> for G2Poly

type Output = G2Poly

The resulting type after applying the - operator.

fn sub(self, rhs: G2Poly) -> G2Poly

Performs the - operation.

impl Mul<G2Poly> for G2Poly

type Output = G2PolyProd

The resulting type after applying the * operator.

fn mul(self, rhs: G2Poly) -> G2PolyProd

Performs the * operation.

impl Div<G2Poly> for G2Poly

type Output = G2Poly

The resulting type after applying the / operator.

fn div(self, rhs: G2Poly) -> G2Poly

Calculate the polynomial quotient

For a / b calculate the value q in a = q * b + r such that |r| < |b|.

Example

let a = G2Poly(0b0100_0000_0101);
let b = G2Poly(0b1010);

assert_eq!(G2Poly(0b101_01010), a / b);

impl Rem<G2Poly> for G2Poly

type Output = G2Poly

The resulting type after applying the % operator.

fn rem(self, rhs: G2Poly) -> G2Poly

Performs the % operation.

impl Rem<G2Poly> for G2PolyProd

type Output = G2Poly

The resulting type after applying the % operator.

fn rem(self, rhs: G2Poly) -> G2Poly

Calculate the polynomial remainder of the product of polynomials

When calculating a % b this computes the value of r in a = q * b + r such that |r| < |b|.

Example

let a = G2Poly(0x12_34_56_78_9A_BC_DE);
let m = G2Poly(0x00_00_00_01_00_00);
assert!((a * a % m).degree().expect("Positive degree") < m.degree().expect("Positive degree"));
assert_eq!(G2Poly(0b0101_0001_0101_0100), a * a % m);