modulo.cpp File Reference

Primary module interface unit for module modulo. More...

#include <algorithm>
#include <cassert>
#include <concepts>
#include <random>
#include <ranges>
#include <type_traits>
import base;

Include dependency graph for modulo.cpp:

Functions
template<Integer T>
constexpr T	ntlib::floor_div (T a, T b) noexcept
	Returns the rounded down quotient of two given numbers.
template<Integer T>
constexpr T	ntlib::ceil_div (T a, T b) noexcept
	Returns the rounded up quotient of two given numbers.
template<Integer T>
constexpr T	ntlib::mod (T a, T m) noexcept
	The mathematical modulo operation.
template<MultiplicativeMonoid A, Integer B, Integer M, std::invocable< A, M > MF>
constexpr A	ntlib::mod_pow (A a, B b, M m, MF mod_func) noexcept
	Binary exponentiation with a custom mod-function and modulus.
template<Integer T>
constexpr T	ntlib::mod_mult_inv (T a, T m) noexcept
	Computes the multiplicative inverse.
template<Integer T>
constexpr bool	ntlib::mod_is_square (T a, T p) noexcept
	Test whether a given number is a quadratic residue module a prime.
template<Integer T>
constexpr T	ntlib::mod_sqrt (T n, T p) noexcept
	Computes square roots moduolo an odd prime.
template<Integer T>
constexpr T	ntlib::mod_factorial (T n, T m)
	Computes a factorial modulo a given number.
template<Integer T>
constexpr T	ntlib::legendre (T a, T p) noexcept
	Computes the Legendre Symbol.
template<Integer T>
constexpr T	ntlib::jacobi (T a, T b) noexcept
	Computes the Jacobi Symbol \(\left(\frac{a}{p}\right)\).

Detailed Description

Primary module interface unit for module modulo.

Function Documentation

ceil_div()

template<Integer T>

T ntlib::ceil_div ( T a, T b )

nodiscardconstexprexportnoexcept

Returns the rounded up quotient of two given numbers.

Template Parameters

T	An integer-like type.

Parameters

a	The dividend.
b	The divisor.

Returns

The quotient, rounded up.

floor_div()

template<Integer T>

T ntlib::floor_div ( T a, T b )

nodiscardconstexprexportnoexcept

Returns the rounded down quotient of two given numbers.

Template Parameters

T	An integer-like type.

Parameters

a	The dividend.
b	The divisor.

Returns

The quotient, rounded down.

jacobi()

template<Integer T>

T ntlib::jacobi ( T a, T b )

nodiscardconstexprexportnoexcept

Computes the Jacobi Symbol \(\left(\frac{a}{p}\right)\).

Template Parameters

T	An integer-like type.

Parameters

a	The "numerator".
b	The "denominator".

Returns

The Jacobi Symbol \(\left(\frac{a}{p}\right)\).

legendre()

template<Integer T>

T ntlib::legendre ( T a, T p )

nodiscardconstexprexportnoexcept

Computes the Legendre Symbol.

For an integer \(a\) and an odd prime \(p\), the Legendre Symbol \(\left(\frac{a}{p}\right)\) determines whether \(a\) is a quadratic residue modulo \(p\).

Template Parameters

T	An integer-like type.

Parameters

a	An integer.
p	An odd prime.

Returns

The Legendre Symbol \(\left(\frac{a}{p}\right)\).

mod()

template<Integer T>

T ntlib::mod ( T a, T m )

nodiscardconstexprexportnoexcept

The mathematical modulo operation.

If the modulus \(m\) is positive, then so is the result.

Template Parameters

T	An integer-like type.

Parameters

a	The number to take modulo \(m\).
m	The modulus.

Returns

\(a \mod m\) in the mathematical sense.

mod_factorial()

template<Integer T>

T ntlib::mod_factorial ( T n, T m )

nodiscardconstexprexport

Computes a factorial modulo a given number.

For \(n, m \in \mathbb{N}\), computes \(n! \mod m\).

Template Parameters

T	An integer-like type.

Parameters

n	The given number.
m	The modulus.

Returns

The factorial \(n!\) modulo \(m\).

mod_is_square()

template<Integer T>

bool ntlib::mod_is_square ( T a, T p )

nodiscardconstexprexportnoexcept

Test whether a given number is a quadratic residue module a prime.

For \(a, p \in \mathbb{N}\) where \(p\) is prime, checks whether \(a\) is a quadratic residue modulo \(p\), i.e., if there is an \(x\) such that \(x^2 = a \mod p\).

Template Parameters

T	An integer-like type.

Parameters

a	The number to test.
p	The modulus. Must be prime.

Returns

Whether \(a\) is a quadratic residue modulo \(p\).

mod_mult_inv()

template<Integer T>

T ntlib::mod_mult_inv ( T a, T m )

nodiscardconstexprexportnoexcept

Computes the multiplicative inverse.

Let \(m \in \mathbb{N}\) and \(a \in \mathbb{Z}/m\mathbb{Z}\) such that \(\mathrm{gcd}(a, m) = 1\). Computes the multiplicative inverse of \(a \mod m\).

Template Parameters

T	A integer-like type.

Parameters

a	The number to invert.
m	The order of the group \(a \in \mathbb{Z}/m\mathbb{Z}\).

Returns

The multiplicative inverse of \(a\) modulo \(m\).

mod_pow()

template<MultiplicativeMonoid A, Integer B, Integer M, std::invocable< A, M > MF>

A ntlib::mod_pow ( A a, B b, M m, MF mod_func )

nodiscardconstexprexportnoexcept

Binary exponentiation with a custom mod-function and modulus.

Let \(\mathrm{mod\_func} \colon A \times M \to A\) be a mod-function. Computes \(\mathrm{mod\_func}(a^b, m)\) using binary exponentation.

Complexity: \(O(\log(b))\) calls to \(\mathrm{mod\_func}\).

Template Parameters

A	A multiplicative monoid.
B	An integer-like type.
M	The type of the modulus.
MF	A function object type with signature A(A, M).

Parameters

a	The base.
b	The exponent, must be non-negative.
m	The modulus.
mod_func	The mod-function.

Returns

The result of \(\mathrm{mod\_func}\) applied to the power \(a^b\) and the modulus \(m\).

mod_sqrt()

template<Integer T>

T ntlib::mod_sqrt ( T n, T p )

nodiscardconstexprexportnoexcept

Computes square roots moduolo an odd prime.

Given \(n \in \mathbb{N}\) and an odd prime \(p\), uses the Tonelli-Shankes algorithm to compute an \(x\) such that \(x^2 = n \mod p\).

For every solution \(0 \leq x < p\), there is a second solution \(p - x\). Returns the smaller one.

Template Parameters

T	An integer-like type.

Parameters

n	Parameter \(n\). Must be \(0 \leq n < p\).
p	Odd prime number.

Returns

The smaller of two solutions \(x\) to \(x^2 = n \mod p\).