gcd(a: int, b: int) -> int
Uses the Euclidean algorithm to calculate the greatest common divisor between two numbers.
\( x = \gcd(a, b) \)
extended_euclidean(a: int, b: int) -> tuple[int, int, int]
Uses the Extended Euclidean algorithm to calculate solutions to the following equation. These solutions are called Bezout coefficients.
\( ax + by = \gcd(a, b) \)
eulers_totient(n: int) -> int
This function calculates Euler's totient function, also known as Euler's phi function, which counts the number of positive integers less than or equal to n that are relatively prime to n.
\( x = \phi(n) \)
is_coprime(a: int, b: int) -> bool
This function checks whether two integers are coprime, i.e., whether their greatest common divisor (GCD) is equal to 1.
\( \gcd(a, b) = 1 \)
fast_exp(a: int, b: int) -> int
This function calculates the exponentiation of an integer 'a' raised to the power of another integer 'b' using an optimized algorithm known as exponentiation by squaring.
\( a^b = x \)
mod_exp(a: int, b: int, m: int) -> int
Uses the fast powering algorithm to exponentiate a number modulus.
\( a^b \equiv x \mod m \)
This works by decomposing the number into a sum of powers of 2. This is already done since computers represent numbers in base 2 (binary).
\( 314 = 100111010_2 = 2^1 + 2^3 + 2^4 + 2^5 + 2^8\)
Then computing \( 2^k \mod m \) for each digit in binary by squaring the previous iteration.