Primary module interface unit for module chinese_remainder. More...

#include <algorithm>
#include <optional>
#include <ranges>
#include <tuple>
#include <type_traits>
#include <vector>
import prime_generation;
import prime_decomposition;
import modulo;
import base;

Include dependency graph for chinese_remainder.cpp:

Classes
struct	ntlib::crt_congruence< T >
	Represents a single congruence x = a mod m. More...

Functions
template<Integer T>
constexpr crt_congruence< T >	ntlib::crt_coprime (const std::vector< crt_congruence< T > > &congruences) noexcept
	Solve a system of modular congruences for pairwise coprime moduli.
template<Integer T>
constexpr std::optional< crt_congruence< T > >	ntlib::crt (const std::vector< crt_congruence< T > > &congruences)
	Solve a general system of modular congruences.

Detailed Description

Primary module interface unit for module chinese_remainder.

Function Documentation

◆ crt()

template<Integer T>

std::optional< crt_congruence< T > > ntlib::crt ( const std::vector< crt_congruence< T > > & congruences )

nodiscardconstexprexport

Solve a general system of modular congruences.

Uses a generalization of the Chinese remainder theorem to handle non-coprime moduli. Either there is no solution, or there is a unique solution modulo \(M = \mathrm{lcm}(m_1, \ldots, m_k)\).

Template Parameters

T	An integer-like type.

Parameters

congruences The list of congruences.

Returns: A std::optional containing the unique solution if it exists.

◆ crt_coprime()

template<Integer T>

crt_congruence< T > ntlib::crt_coprime ( const std::vector< crt_congruence< T > > & congruences )

nodiscardconstexprexportnoexcept

Solve a system of modular congruences for pairwise coprime moduli.

Uses the Chinese remainder theorem in its classical form. A solution always exists and is unique modulo \(M = \Pi_i m_i\).