Struct Modulo

Source

pub struct Modulo<'a, U> { /* private fields */ }

Expand description

Modulo with a runtime-specified odd modulus.

§Usage

use lib_modulo::Context64;

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

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

§Caution

Modulo values created from different Contexts can technically interact, but the results will be meaningless. It is recommended to use a block to ensure that each Context is dropped before another one is introduced.

Implementations§

Source §

impl<'a> Modulo<'a, u64>

Source

pub const fn get(&self) -> u64

Returns value.

§Example

use lib_modulo::Context;

let n = 101;
let ctx = Context::<u64>::new(n);

let n = ctx.modulo(99);

assert_eq!(n.get(), 99);
assert_eq!(n.modulus(), 101);

Source

pub const fn modulus(&self) -> u64

Returns modulus.

§Example

use lib_modulo::Context;

let n = 101;
let ctx = Context::<u64>::new(n);

let n = ctx.modulo(99);

assert_eq!(n.get(), 99);
assert_eq!(n.modulus(), 101);

Source

pub const fn is_zero(self) -> bool

Returns true if self is 0.

§Example

use lib_modulo::Context;

for n in (1..100_000).step_by(2) {
    let ctx = Context::<u64>::new(n);
    assert!(ctx.modulo(0).is_zero());
}

Source

pub const fn zero(ctx: &'a Context<u64>) -> Self

Returns 0.

§Example

use lib_modulo::{Context, Modulo};

for n in (1..100_000).step_by(2) {
    let ctx = Context::<u64>::new(n);
    assert_eq!(Modulo::<'_, u64>::zero(&ctx).get(), 0);
}

Source

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::Context;

let n = 12_345;
let ctx = Context::<u64>::new(n);

let mut pow10 = 1;
for i in 0..1_000 {
    assert_eq!(ctx.modulo(10).pow(i).get(), pow10);
    pow10 = pow10 * 10 % n;
}

Source

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

§Time complexity

O(log self)

§Example

use lib_modulo::Context;

// 998_244_353 is a prime number, so modular inverse of n exists iff n != 0 (mod 998_244_353)
let ctx = Context::<u64>::new(998_244_353);

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

Source §

impl<'a> Modulo<'a, u32>

Source

pub const fn get(&self) -> u32

Returns value.

§Example

use lib_modulo::Context;

let n = 101;
let ctx = Context::<u32>::new(n);

let n = ctx.modulo(99);

assert_eq!(n.get(), 99);
assert_eq!(n.modulus(), 101);

Source

pub const fn modulus(&self) -> u32

Returns modulus.

§Example

use lib_modulo::Context;

let n = 101;
let ctx = Context::<u32>::new(n);

let n = ctx.modulo(99);

assert_eq!(n.get(), 99);
assert_eq!(n.modulus(), 101);

Source

pub const fn is_zero(self) -> bool

Returns true if self is 0.

§Example

use lib_modulo::Context;

for n in (1..100_000).step_by(2) {
    let ctx = Context::<u32>::new(n);
    assert!(ctx.modulo(0).is_zero());
}

Source

pub const fn zero(ctx: &'a Context<u32>) -> Self

Returns 0.

§Example

use lib_modulo::{Context, Modulo};

for n in (1..100_000).step_by(2) {
    let ctx = Context::<u32>::new(n);
    assert_eq!(Modulo::<'_, u32>::zero(&ctx).get(), 0);
}

Source

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

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

§Time complexity

O(log exp)

§Example

use lib_modulo::Context;

let n = 12_345;
let ctx = Context::<u32>::new(n);

let mut pow10 = 1;
for i in 0..1_000 {
    assert_eq!(ctx.modulo(10).pow(i).get(), pow10);
    pow10 = pow10 * 10 % n;
}

Source

pub const fn try_inv(self) -> Result<Self, u32>

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::Context;

// 998_244_353 is a prime number, so modular inverse of n exists iff n != 0 (mod 998_244_353)
let ctx = Context::<u32>::new(998_244_353);

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