Struct Modulus32Any

Source

pub struct Modulus32Any { /* private fields */ }

Expand description

A modulus in [2, 2^32), including even values.

§Fast modular multiplication

Provides fast modular multiplication using Barrett multiplication. This works for any modulus (including even ones) and places no restrictions on the operands, but is generally slower than Residue32.

Unlike Montgomery or Plantard methods, this operates directly on standard integer representations (i.e., no transformation is required).

§Usage

use lib_modulo::Modulus32Any;

let modulus = Modulus32Any::new(14).unwrap();
assert_eq!(modulus.mul(3, 5), 1)

Implementations§

Source §

impl Modulus32Any

Source

pub const fn new(n: u32) -> Result<Self, InvalidModulus>

Creates new instance with the given modulus.

§Error

Returns error if the given modulus is 0 or 1.

§Example

use lib_modulo::{Modulus32Any, InvalidModulus};

// even number is available
let modulus = Modulus32Any::new(2).unwrap();
// odd number is also available
let modulus = Modulus32Any::new(3).unwrap();
// division by 0 is undefined
assert_eq!(Modulus32Any::new(0), Err(InvalidModulus::Zero));
// division by 1 is meaningless and NOT available for performance
assert_eq!(Modulus32Any::new(1), Err(InvalidModulus::One));

Source

pub const fn modulus(&self) -> u32

Returns the modulus.

Source

pub const fn residue32(&self, x: u32) -> u32

Calculates residue of x modulo self.

Source

pub const fn residue64(&self, x: u64) -> u64

Calculates residue of x modulo self.

Source

pub const fn can_divide(&self, x: u32) -> bool

Checks if x is divisible by self.

Source

pub const fn mul(&self, a: u32, b: u32) -> u32

Performs a * b modulo self.

§Example

use lib_modulo::Modulus32Any;

// even number is available
let modulus = Modulus32Any::new(1 << 8).unwrap();
assert_eq!(modulus.mul(u32::MAX, u32::MAX), 1);

Source

pub const fn carrying_mul(&self, a: u32, b: u32, c: u32) -> u32

Performs a * b + c modulo self.

§Example

use lib_modulo::Modulus32Any;

let modulus = Modulus32Any::new(2357).unwrap();
assert_eq!(
    modulus.carrying_mul(123, 456, 789),
    (123 * 456 + 789) % 2357
);

Source

pub const fn carrying_mul_add(&self, a: u32, b: u32, c: u32, d: u32) -> u32

Performs a * b + c + d modulo self.

§Example

use lib_modulo::Modulus32Any;

// even number is available
let modulus = Modulus32Any::new(123_456).unwrap();
assert_eq!(
    modulus.carrying_mul_add(u32::MAX, u32::MAX, u32::MAX, u32::MAX),
    (u64::MAX % 123_456) as u32
);

Source

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

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

§Time Complexity

O(log x)

§Example

use lib_modulo::Modulus32Any;

let modulus = Modulus32Any::new(123_456).unwrap();

assert_eq!(modulus.pow(123_456 * 100 + 1, 1000), 1)

Source

pub const fn inv(&self, x: u32) -> Result<u32, u32>

Calculates the modular inverse of x, using extended gcd algorithm.

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

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

§Time complexity

O(log x)

§Example

use lib_modulo::Modulus32Any;

let modulus = Modulus32Any::new(3 * 5).unwrap();
for (a, inv_a) in [(1, 1), (2, 8), (4, 4), (7, 13), (11, 11), (14, 14)] {
    assert_eq!(modulus.mul(a, inv_a), 1);
    assert_eq!(modulus.inv(a), Ok(inv_a));
}
for a in [3, 6, 9, 12] {
    assert_eq!(modulus.inv(a), Err(3));
}
for a in [5, 10] {
    assert_eq!(modulus.inv(a), Err(5));
}
// gcd(0, a) is defined t be `a`
assert_eq!(modulus.inv(0), Err(15));
assert_eq!(modulus.inv(15 * 99), Err(15));