modular_arithmetic.H File Reference

Safe modular arithmetic, extended Euclidean algorithm, and Chinese Remainder Theorem. More...

#include <cstdint>
#include <type_traits>
#include <ah-errors.H>
#include <tpl_array.H>

Include dependency graph for modular_arithmetic.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
uint64_t	Aleph::mod_mul (uint64_t a, uint64_t b, uint64_t m)
	Safe 64-bit modular multiplication.
uint64_t	Aleph::mod_exp (uint64_t base, uint64_t exp, const uint64_t m)
	Modular exponentiation.
template<typename T > requires (std::is_integral_v<T> and std::is_signed_v<T>)
T	Aleph::ext_gcd (T a, T b, T &x, T &y) noexcept
	Extended Euclidean Algorithm.
uint64_t	Aleph::mod_inv (const uint64_t a, const uint64_t m)
	Modular Inverse.
uint64_t	Aleph::crt (const Array< uint64_t > &rem, const Array< uint64_t > &mod)
	Chinese Remainder Theorem (CRT).

Detailed Description

Safe modular arithmetic, extended Euclidean algorithm, and Chinese Remainder Theorem.

Provides 64-bit safe modular arithmetic using 128-bit integers internally to prevent overflow, along with standard number theory algorithms like extended GCD, modular inverse, and the Chinese Remainder Theorem.

Definition in file modular_arithmetic.H.