#pragma once #include "funconfig.h" #include #include // Common public exponent, in Fermat prime form #define PUBEXP ((1 << 16) | 0x1) /** * @brief Calculates greatest common divider of two integers using the euclidean * algorithm * * @param a First number * @param b Second number * @return The greatest common divider */ u64 gcd(u64 a, u64 b); /** * @brief Computes Euler's Totient function φ(n), which counts the number of * integers from 1 to n that are coprime to n. * * @param n The input number. * @return The number of integers from 1 to n that are coprime to n. */ u64 totient(u64 n); /** * @brief Computes (a * b) % m safely without overflow. * * Uses repeated addition and bit shifting to handle large values, * ensuring correctness even on 32-bit microcontrollers. * * @param a The first operand. * @param b The second operand. * @param m The modulus. * @return (a * b) % m computed safely. */ u64 mulmod(u64 a, u64 b, u64 m); /** * @brief Modular exponentiation (a^b) mod m * * @param a The base * @param b The exponent * @param m The modulus */ u64 modexp(u64 a, u64 b, u64 m); /** * @brief Computes the modular inverse of a modulo m. * * @param a The integer whose modular inverse is to be found. * @param m The modulus. * @return The modular inverse of a modulo m, or -1 if no inverse exists. */ u64 mod_inverse(u64 a, u64 m); /** * @brief Generates a random prime number within the given range. * * @param min The lower bound (inclusive). * @param max The upper bound (inclusive). * @return A prime number in the range [min, max]. */ u64 gen_prime(u64 min, u64 max); /** * @brief Checks if a number is prime. * * @param n The number to check. * @return true if n is prime, false otherwise. */ bool is_prime(u64 n); /** * @brief Performs the Miller-Rabin primality test to check if a number is * probably prime. * * @param n The number to test for primality. * @param k The number of rounds of testing to perform. * @return true if n is probably prime, false if n is composite. */ bool miller_rabin(u64 n, u64 k); /** * @brief Computes the greatest common divisor (GCD) of two integers a and b * using the Extended Euclidean Algorithm. Also finds coefficients x and y such * that ax + by = gcd(a, b). * * @param a The first integer. * @param b The second integer. * @param x Pointer to an integer to store the coefficient x in the equation ax * + by = gcd(a, b). * @param y Pointer to an integer to store the coefficient y in the equation ax * + by = gcd(a, b). * @return The greatest common divisor (gcd) of a and b. */ u64 extended_euclid(u64 a, u64 b, u64 *x, u64 *y);