Struct Residue32 

pub struct Residue32<'a> { /* private fields */ }

A residue with an odd modulus not exceeding 2_654_435_769.

Fast modular multiplication

Residue32 provides fast modular multiplication using Plantard multiplication. This method eliminates one multiplication when one of the operands is reused multiple times. As a result, Residue32::pow and other operations are typically faster than implementations based on Montgomery multiplication.

Usage

use lib_modulo::Modulus32;

// set modulus
let modulus = Modulus32::new(3);

// performs modular arithmetic
let one = modulus.residue(1);
let two = modulus.residue(2);
let five = modulus.residue(5);
assert_eq!(two * five, one)

Two residues with different modulus can interact, but the result will be meaningless. It is highly recommended to use a block to ensure that Modulus32, therefore Residue32s, are dropped.

Implementations

impl<'a> Residue32<'a>

pub const fn into_raw(self) -> Raw32

Extract the internal representation of self.

use lib_modulo::{Modulus32, Raw32};

let modulus = Modulus32::new(1001);
// save memory
let residues: Vec<Raw32> = (1..=1000).map(|x| modulus.residue(x).into_raw()).collect();

pub const fn is_zero(self) -> bool

Checks whether self is 0.

Example

use lib_modulo::Modulus32;

let modulus = Modulus32::new(5);
assert!(modulus.residue(10).is_zero())

pub const fn get(self) -> u64

Returns the residue.

Example

use lib_modulo::Modulus32;

let modulus = Modulus32::new(7);
assert_eq!(modulus.residue(10).get(), 3)

pub const fn modulus(&self) -> u64

Returns the modulus.

Example

use lib_modulo::Modulus32;

let modulus = Modulus32::new(11);
assert_eq!(modulus.residue(2).modulus(), 11);

pub const fn pow(self, exp: u32) -> Self

Raises self to the power of exp, using exponentiation by squaring.

Time complexity

Θ(log exp)

Example

use lib_modulo::Modulus32;

let modulus = Modulus32::new(1001);
let residue = modulus.residue(2);
for exp in 0..64 {
    assert_eq!(residue.pow(exp).get(), (1 << exp) % 1001)
}

pub const fn inv(self) -> Result<Self, u64>

Calculates the modular inverse of self, using extended binary GCD algorithm.

Modular inverse can be defined if and only if self and the modulus is coprime.

• Ok(x) : x is the modular inverse.
• Err(x): x is the GCD of self and the modulus, where gcd(0, a) is defined to be a.

Time complexity

O(log self)

Example

use lib_modulo::Modulus32;

let modulus = Modulus32::new(3 * 5);

let residue = modulus.residue(2);
assert!(residue.inv().is_ok_and(|inv| (inv * residue).get() == 1));

let residue = modulus.residue(6);
assert!(residue.inv().is_err_and(|gcd| gcd == 3));

Trait Implementations

impl<'a> Add for Residue32<'a>

type Output = Residue32<'a>

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self::Output

Performs the + operation.

impl<'a> AddAssign for Residue32<'a>

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl<'a> Clone for Residue32<'a>

fn clone(&self) -> Residue32<'a>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<'a> Debug for Residue32<'a>

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

Formats the value using the given formatter.

impl<'a> From<Residue32<'a>> for Raw32

fn from(residue: Residue32<'a>) -> Self

Converts to this type from the input type.

impl<'a> Hash for Residue32<'a>

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<'a> Mul for Residue32<'a>

type Output = Residue32<'a>

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation.

impl<'a> MulAssign for Residue32<'a>

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation.

impl<'a> Neg for Residue32<'a>

type Output = Residue32<'a>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<'a> PartialEq for Residue32<'a>

fn eq(&self, other: &Residue32<'a>) -> 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<'a> Sub for Residue32<'a>

type Output = Residue32<'a>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation.

impl<'a> SubAssign for Residue32<'a>

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation.

impl<'a> Copy for Residue32<'a>

impl<'a> Eq for Residue32<'a>

impl<'a> StructuralPartialEq for Residue32<'a>