Struct Residue64 

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

A residue with an odd modulus that fits in 2^64.

Fast modular multiplication

Residue64 provides fast modular multiplication using Montgomery multiplication. Since this method provides modular multiplication without division, it is approximately twice as fast.

Usage

use lib_modulo::Modulus64;

// runtime-specified *odd* modulus
let modulus = 5;

let modulus = Modulus64::new(modulus); // slow
let n = modulus.residue(2) * modulus.residue(3); // fast
assert_eq!(n.get(), 1);

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

Implementations

impl Residue64<'_>

pub const fn into_raw(self) -> Raw64

Extract the internal representation of self.

use lib_modulo::{Modulus64, Raw64};

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

// `Residue64` and `raw64` can interact.
// The caller must ensure that both operands shares the same modulus.
let double_sum = residues.into_iter().fold(modulus.residue(0), |sum, r| r + sum + r);
assert_eq!(double_sum, modulus.residue((1 + 1000) * 1000));

pub const fn get(&self) -> u64

Returns the residue.

Example

use lib_modulo::Modulus64;

let modulus  = Modulus64::new(5);
let n = modulus.residue(7);
assert_eq!(n.get(), 2);

pub const fn modulus(&self) -> u64

Returns the modulus.

Example

use lib_modulo::Modulus64;

let modulus  = Modulus64::new(5);
let n = modulus.residue(7);
assert_eq!(n.modulus(), 5);

pub const fn is_zero(self) -> bool

Checks whether self is 0.

Example

use lib_modulo::Modulus64;

let modulus  = Modulus64::new(3);
assert_eq!(modulus.residue(6).get(), 0);

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

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

Time complexity

O(log exp)

Example

use lib_modulo::Modulus64;

let modulus = Modulus64::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) = gcd(a, 0) is defined to be a.

Time complexity

O(log self)

Example

use lib_modulo::Modulus64;

// 998_244_353 is a prime number, so modular inverse of n exists iff n != 0 (mod 998_244_353)
let modulus = Modulus64::new(998_244_353);

for n in 1..500_000 {
    let n = modulus.residue(n);
    assert!(n.inv().is_ok_and(|i| (i * n).get() == 1));
}
// 0 n = 0 != 1 for any integer n
assert!(modulus.residue(0).inv().is_err());

Trait Implementations

impl<'a> Add<Raw64> for Residue64<'a>

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

Performs the + operation.

Caution

The caller must ensure that both operands shares the same modulus.

type Output = Residue64<'a>

The resulting type after applying the + operator.

impl<'a> Add<Residue64<'a>> for Raw64

fn add(self, rhs: Residue64<'a>) -> Self::Output

Performs the + operation.

Caution

The caller must ensure that both operands shares the same modulus.

type Output = Residue64<'a>

The resulting type after applying the + operator.

impl Add for Residue64<'_>

type Output = Residue64<'_>

The resulting type after applying the + operator.

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

Performs the + operation.

impl AddAssign<Raw64> for Residue64<'_>

fn add_assign(&mut self, rhs: Raw64)

Performs the += operation.

Caution

The caller must ensure that both operands shares the same modulus.

impl AddAssign for Residue64<'_>

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl<'a> Clone for Residue64<'a>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<'a> Debug for Residue64<'a>

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

Formats the value using the given formatter.

impl<'a> From<Residue64<'a>> for Raw64

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

Converts to this type from the input type.

impl<'a> Hash for Residue64<'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<Raw64> for Residue64<'a>

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

Performs the * operation.

Caution

The caller must ensure that both operands shares the same modulus.

type Output = Residue64<'a>

The resulting type after applying the * operator.

impl<'a> Mul<Residue64<'a>> for Raw64

fn mul(self, rhs: Residue64<'a>) -> Self::Output

Performs the * operation.

Caution

The caller must ensure that both operands shares the same modulus.

type Output = Residue64<'a>

The resulting type after applying the * operator.

impl Mul for Residue64<'_>

type Output = Residue64<'_>

The resulting type after applying the * operator.

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

Performs the * operation.

impl MulAssign<Raw64> for Residue64<'_>

fn mul_assign(&mut self, rhs: Raw64)

Performs the *= operation.

Caution

The caller must ensure that both operands shares the same modulus.

impl MulAssign for Residue64<'_>

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation.

impl Neg for Residue64<'_>

type Output = Residue64<'_>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<'a> PartialEq for Residue64<'a>

fn eq(&self, other: &Residue64<'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<Raw64> for Residue64<'a>

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

Performs the - operation.

Caution

The caller must ensure that both operands shares the same modulus.

type Output = Residue64<'a>

The resulting type after applying the - operator.

impl<'a> Sub<Residue64<'a>> for Raw64

fn sub(self, rhs: Residue64<'a>) -> Self::Output

Performs the - operation.

Caution

The caller must ensure that both operands shares the same modulus.

type Output = Residue64<'a>

The resulting type after applying the - operator.

impl Sub for Residue64<'_>

type Output = Residue64<'_>

The resulting type after applying the - operator.

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

Performs the - operation.

impl SubAssign<Raw64> for Residue64<'_>

fn sub_assign(&mut self, rhs: Raw64)

Performs the -= operation.

Caution

The caller must ensure that both operands shares the same modulus.

impl SubAssign for Residue64<'_>

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation.

impl<'a> Copy for Residue64<'a>

impl<'a> Eq for Residue64<'a>

impl<'a> StructuralPartialEq for Residue64<'a>