\( (n, t) \) Number Theory

Common Functions

Greatest Common Divisor

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 Algorithm

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

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


Coprime Test

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 Exponentiation

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


Modular exponentiation

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.