Struct Modulo

pub struct Modulo<const M: i64> {
    pub val: i64,
}

Represents an element of the finite (Galois) field of prime order M, where 1 <= M < 2^31.5. If M is not prime, ring operations are still valid but recip() and division are not. Note that the latter operations are also the slowest, so precompute any inverses that you intend to use frequently.

Fields

val: i64

Implementations

impl<const M: i64> Modulo<M>

pub fn pow(self, n: u64) -> Self

Computes self^exp in O(log n) time

pub fn vec_of_recips(n: i64) -> Vec<Self>

Computes inverses of 1 to n in O(n) time

pub fn recip(self) -> Self

Computes self^-1 in O(log M) time

Trait Implementations

impl<const M: i64> Add for Modulo<M>

type Output = Modulo<M>

The resulting type after applying the + operator.

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

Performs the + operation.

impl<const M: i64> Clone for Modulo<M>

fn clone(&self) -> Modulo<M>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<const M: i64> Debug for Modulo<M>

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

Formats the value using the given formatter.

impl<const M: i64> Div for Modulo<M>

type Output = Modulo<M>

The resulting type after applying the / operator.

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

Performs the / operation.

impl<const M: i64> From<i64> for Modulo<M>

fn from(val: i64) -> Self

Converts to this type from the input type.

impl<const M: i64> Hash for Modulo<M>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<const M: i64> Mul for Modulo<M>

type Output = Modulo<M>

The resulting type after applying the * operator.

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

Performs the * operation.

impl<const M: i64> Neg for Modulo<M>

type Output = Modulo<M>

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl<const M: i64> PartialEq for Modulo<M>

fn eq(&self, other: &Modulo<M>) -> 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<const M: i64> Sub for Modulo<M>

type Output = Modulo<M>

The resulting type after applying the - operator.

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

Performs the - operation.

impl<const M: i64> Copy for Modulo<M>

impl<const M: i64> Eq for Modulo<M>

impl<const M: i64> StructuralPartialEq for Modulo<M>