Struct Modexp 

pub struct Modexp {}

A struct that provides methods for modular exponentiation and modular inverse calculations.

Implementations

impl Modexp

pub fn mod_exp(base: u64, exponent: u64, modulus: u64) -> u64

Calculates (base^exponent) % modulus using modular exponentiation.

Arguments

• base - The base.
• exponent - The exponent.
• modulus - The modulus.

pub fn mod_inv(x: u64, modulus: u64) -> u64

Calculates the modular multiplicative inverse of x modulo modulus.

The modular inverse of x modulo modulus is an integer y such that (x * y) % modulus == 1. It exists if and only if x and modulus are coprime (i.e., their greatest common divisor is 1).

This function uses Fermat’s Little Theorem, which states that if modulus is a prime number, then for any integer x not divisible by modulus, x ^ (modulus - 1) ≡ 1 (mod modulus). Therefore, the modular inverse of x is x ^ (modulus - 2) (mod modulus).

Arguments

• x - The number for which to calculate the inverse.
• modulus - The modulus.

Returns

The modular inverse of x modulo modulus.

Panics

This function will panic if:

• modulus is 0.
• x and modulus are not coprime (their greatest common divisor is not 1).