Trait Mod 

pub trait Mod: Sized + Sealed {
    type Native;

    const MODULUS: Self::Native;
    const ZERO: Self;
    const ONE: Self;

    // Required methods
    fn new(x: Self::Native) -> Self;
    unsafe fn new_unchecked(x: Self::Native) -> Self;
    fn remainder(self) -> Self::Native;
    fn to_raw(self) -> Self::Native;
    fn is<const C: u64>(self) -> bool;
    fn is_zero(&self) -> bool;
    fn pow(self, n: u64) -> Self;
    fn is_invertible(&self) -> bool;
    fn inverse(self) -> Option<Self>;
}

A common interface for modular arithmetic.

This trait is implemented by all types in this crate.

Required Associated Constants

const MODULUS: Self::Native

The value of the modulus, or 0 if it is a power of two.

0 is used because the full value 2^k does not fit in a k-bit integer, so it overflows to 0.

const ZERO: Self

A constant 0 value.

const ONE: Self

A constant 1 value.

Required Associated Types

type Native

The underlying native type.

Required Methods

fn new(x: Self::Native) -> Self

Create a value corresponding to x mod m.

unsafe fn new_unchecked(x: Self::Native) -> Self

Create a value corresponding to x, assuming x is a correct representation for this type.

This function is most useful for prime moduli, since it’s faster than new for those types.

Safety

This function is safe to call if either of the two conditions holds:

• x is less than the modulus, or
• x was produced by to_raw on the same type.

fn remainder(self) -> Self::Native

Get the normalized residue x mod m.

fn to_raw(self) -> Self::Native

Get the internal optimized representation of the number.

This returns some value equivalent to x modulo m, but not necessarily x mod m itself. This is more efficient than remainder for prime moduli. Passing this value to new or new_unchecked is guaranteed to produce the same value as self.

fn is<const C: u64>(self) -> bool

Compare for equality with a constant.

For fast moduli, this is more efficient than x == FastK::new(C). C must be a valid reminder, i.e. C < m.

C is typed u64 instead of Native due to Rust having issues with associated types in const.

fn is_zero(&self) -> bool

Compare for equality with zero.

This is equivalent to is::<0>().

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

Compute x^n mod m.

The current implementation uses iterative binary exponentiation, combining it with the Carmichael function to reduce exponents. It works in O(log n).

fn is_invertible(&self) -> bool

Check if the value is invertible, i.e. if x is coprime with m.

The current implementation checks x % p != 0 for all prime factors p of the modulus. This is very fast for PowerK, relatively fast for PrimeK/BigPrimeK and slightly slow for FastK.

fn inverse(self) -> Option<Self>

Compute the multiplicative inverse.

Returns None if x is not coprime with m.

For power-of-two moduli, the current implementation uses an algorithm by Hurchalla, which works in O(log k). For other moduli, it uses a variation of Pornin’s algorithm, which works in O(k).

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl Mod for BigPrime8

const MODULUS: u8 = 251u8

const ZERO: Self

const ONE: Self

type Native = u8

impl Mod for BigPrime16

const MODULUS: u16 = 65_521u16

const ZERO: Self

const ONE: Self

type Native = u16

impl Mod for BigPrime32

const MODULUS: u32 = 4_294_967_291u32

const ZERO: Self

const ONE: Self

type Native = u32

impl Mod for BigPrime64

const MODULUS: u64 = 18_446_744_073_709_551_557u64

const ZERO: Self

const ONE: Self

type Native = u64

impl Mod for Fast8

const MODULUS: u8 = 255u8

const ZERO: Self

const ONE: Self

type Native = u8

impl Mod for Fast16

const MODULUS: u16 = 65_535u16

const ZERO: Self

const ONE: Self

type Native = u16

impl Mod for Fast32

const MODULUS: u32 = 4_294_967_295u32

const ZERO: Self

const ONE: Self

type Native = u32

impl Mod for Fast64

const MODULUS: u64 = 18_446_744_073_709_551_615u64

const ZERO: Self

const ONE: Self

type Native = u64

impl Mod for Power8

const MODULUS: u8 = 0u8

const ZERO: Self

const ONE: Self

type Native = u8

impl Mod for Power16

const MODULUS: u16 = 0u16

const ZERO: Self

const ONE: Self

type Native = u16

impl Mod for Power32

const MODULUS: u32 = 0u32

const ZERO: Self

const ONE: Self

type Native = u32

impl Mod for Power64

const MODULUS: u64 = 0u64

const ZERO: Self

const ONE: Self

type Native = u64

impl Mod for Prime7

const MODULUS: u8 = 127u8

const ZERO: Self

const ONE: Self

type Native = u8

impl Mod for Prime13

const MODULUS: u16 = 8_191u16

const ZERO: Self

const ONE: Self

type Native = u16

impl Mod for Prime31

const MODULUS: u32 = 2_147_483_647u32

const ZERO: Self

const ONE: Self

type Native = u32

impl Mod for Prime61

const MODULUS: u64 = 2_305_843_009_213_693_951u64

const ZERO: Self

const ONE: Self

type Native = u64