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 arithmetics
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 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 try_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.try_inv().is_ok_and(|inv| (inv * residue).get() == 1));

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

pub fn log<S>(self, rhs: u32, map: &mut HashMap<u64, u32, S>) -> Option<u32>

where S: BuildHasher,

Solves discrete logarithm problem and returns the smallest solution.

Consider using FxHashMap or other fast hash maps.

Time complexity

O(√modulus)

Example

use lib_modulo::Modulus32;
use std::collections::HashMap;

let modulus = Modulus32::new(2025);
let mut map = HashMap::new();
let mut offset = 0;
for d in 0..5000 {
    let pow2 = modulus.residue(2).pow(d).get() as u32;
    if pow2 == 1 {
        offset = d;
    }
    assert_eq!(modulus.residue(2).log(pow2, &mut map), Some(d - offset));
}
// Since `5 + 2025 i` is multiple of 5, it is not power of 2, 3, or 7
assert!(modulus.residue(2).log(5, &mut map).is_none());
assert!(modulus.residue(3).log(5, &mut map).is_none());
assert!(modulus.residue(7).log(5, &mut map).is_none());

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