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);
assert_eq!(modulus.mul(3, 5), 1)

Implementations§

Source §

impl Modulus32Any

Source

pub const fn new(n: u32) -> Self

Creates new instance with the given modulus.

§Panics

Modulus n should be greater than 1.

§Example

use lib_modulo::Modulus32Any;

// even number is available
let modulus = Modulus32Any::new(2);
// odd number is also available
let modulus = Modulus32Any::new(3);
// division by 0 is undefined
assert!(std::panic::catch_unwind(|| Modulus32Any::new(0)).is_err());
// meaningless division by 1 is NOT available for performance
assert!(std::panic::catch_unwind(|| Modulus32Any::new(1)).is_err());

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 modular multiplication.

§Example

use lib_modulo::Modulus32Any;

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

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

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

Source

pub 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);
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));