Struct G2Poly

Source
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

Source

pub const UNIT: G2Poly

The constant 1 polynomial.

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

Source

pub const ZERO: G2Poly

The constant 0 polynomial

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

Source

pub const X: G2Poly

The x polynomial.

Useful for quickly generating x^n values.

Source

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

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

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

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 Add for G2Poly

Source§

type Output = G2Poly

The resulting type after applying the + operator.
Source§

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

Performs the + operation. Read more
Source§

impl Clone for G2Poly

Source§

fn clone(&self) -> G2Poly

Returns a copy of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

impl Debug for G2Poly

Source§

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

Formats the value using the given formatter. Read more
Source§

impl Display for G2Poly

Source§

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

Formats the value using the given formatter. Read more
Source§

impl Div for G2Poly

Source§

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

type Output = G2Poly

The resulting type after applying the / operator.
Source§

impl Mul for G2Poly

Source§

type Output = G2PolyProd

The resulting type after applying the * operator.
Source§

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

Performs the * operation. Read more
Source§

impl Ord for G2Poly

Source§

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

This method returns an Ordering between self and other. Read more
1.21.0 · Source§

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

Compares and returns the maximum of two values. Read more
1.21.0 · Source§

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

Compares and returns the minimum of two values. Read more
1.50.0 · Source§

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

Restrict a value to a certain interval. Read more
Source§

impl PartialEq for G2Poly

Source§

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

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

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

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

impl PartialOrd for G2Poly

Source§

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

This method returns an ordering between self and other values if one exists. Read more
1.0.0 · Source§

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

Tests less than (for self and other) and is used by the < operator. Read more
1.0.0 · Source§

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

Tests less than or equal to (for self and other) and is used by the <= operator. Read more
1.0.0 · Source§

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

Tests greater than (for self and other) and is used by the > operator. Read more
1.0.0 · Source§

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

Tests greater than or equal to (for self and other) and is used by the >= operator. Read more
Source§

impl Rem for G2Poly

Source§

type Output = G2Poly

The resulting type after applying the % operator.
Source§

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

Performs the % operation. Read more
Source§

impl Sub for G2Poly

Source§

type Output = G2Poly

The resulting type after applying the - operator.
Source§

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

Performs the - operation. Read more
Source§

impl Copy for G2Poly

Source§

impl Eq for G2Poly

Source§

impl StructuralPartialEq for G2Poly

Auto Trait Implementations§

§

impl Freeze for G2Poly

§

impl RefUnwindSafe for G2Poly

§

impl Send for G2Poly

§

impl Sync for G2Poly

§

impl Unpin for G2Poly

§

impl UnwindSafe for G2Poly

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T> ToString for T
where T: Display + ?Sized,

Source§

fn to_string(&self) -> String

Converts the given value to a String. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.