Exact polynomial multiplication via three-prime NTT + CRT. More...

#include <ntt.H>

Collaboration diagram for Aleph::NTTExact:

Classes
struct	CoefficientStats

Public Types
using	coeff_type = __uint128_t

Static Public Member Functions
static constexpr size_t	prime_count () noexcept
	Number of CRT primes in the exact multiplier.

static constexpr coeff_type	exact_modulus_product () noexcept
	Product of the three CRT moduli.

static constexpr bool	supports_product_size (const size_t required) noexcept
	Check whether a target product length is supported.

static Array< coeff_type >	multiply (const Array< uint64_t > &a, const Array< uint64_t > &b)
	Exact sequential polynomial multiplication.

static Array< coeff_type >	pmultiply (ThreadPool &pool, const Array< uint64_t > &a, const Array< uint64_t > &b, const size_t chunk_size=0)
	Exact parallel polynomial multiplication.

Private Types
using	Prime0NTT = NTT< 998244353ULL, 3ULL >

using	Prime1NTT = NTT< 469762049ULL, 3ULL >

using	Prime2NTT = NTT< 1004535809ULL, 3ULL >

Static Private Member Functions
static constexpr coeff_type	exact_modulus_product_impl () noexcept

static constexpr uint64_t	sub_mod (const uint64_t lhs, const uint64_t rhs, const uint64_t mod) noexcept

static constexpr coeff_type	add_capped (const coeff_type lhs, const coeff_type rhs, const coeff_type cap) noexcept

static constexpr coeff_type	mul_capped (const coeff_type lhs, const coeff_type rhs, const coeff_type cap) noexcept

static constexpr size_t	next_power_of_two (const size_t n) noexcept

template<typename PrimeNTT >
static constexpr bool	prime_supports_product_size (const size_t required) noexcept

static std::string	coeff_to_string (coeff_type value)

static CoefficientStats	analyze_coefficients (const Array< uint64_t > &input)

static coeff_type	conservative_bound (const Array< uint64_t > &a, const Array< uint64_t > &b)

static void	validate_inputs (const Array< uint64_t > &a, const Array< uint64_t > &b, const char *const ctx)

static coeff_type	reconstruct_coefficient (const uint64_t r0, const uint64_t r1, const uint64_t r2)

static Array< coeff_type >	reconstruct_product (const Array< uint64_t > &c0, const Array< uint64_t > &c1, const Array< uint64_t > &c2, ThreadPool *const pool, const size_t chunk_size)

Static Private Attributes
static constexpr NTTPrime	primes_ []

Detailed Description

Exact polynomial multiplication via three-prime NTT + CRT.

This helper reconstructs coefficients in __uint128_t using three standard NTT-friendly primes:

998244353 = 119 * 2^23 + 1
469762049 = 7 * 2^26 + 1
1004535809 = 479 * 2^21 + 1

The result is exact as long as every coefficient of the true convolution lies in [0, P), where P is the product of the three moduli. Before executing the transforms, the implementation applies conservative sufficient bounds and rejects inputs that cannot be proven to fit inside that CRT range.

Definition at line 2389 of file ntt.H.

Member Typedef Documentation

◆ coeff_type

using Aleph::NTTExact::coeff_type = __uint128_t

Definition at line 2392 of file ntt.H.

◆ Prime0NTT

using Aleph::NTTExact::Prime0NTT = NTT<998244353ULL, 3ULL>

private

Definition at line 2395 of file ntt.H.

◆ Prime1NTT

using Aleph::NTTExact::Prime1NTT = NTT<469762049ULL, 3ULL>

private

Definition at line 2396 of file ntt.H.

◆ Prime2NTT

using Aleph::NTTExact::Prime2NTT = NTT<1004535809ULL, 3ULL>

private

Definition at line 2397 of file ntt.H.

Member Function Documentation

◆ add_capped()

static constexpr coeff_type Aleph::NTTExact::add_capped	(	const coeff_type	lhs,
		const coeff_type	rhs,
		const coeff_type	cap
	)

inlinestaticconstexprprivatenoexcept

Definition at line 2429 of file ntt.H.

◆ analyze_coefficients()

static CoefficientStats Aleph::NTTExact::analyze_coefficients ( const Array< uint64_t > & input )

inlinestaticprivate

Definition at line 2496 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::NTTExact::CoefficientStats::max_value, Aleph::NTTExact::CoefficientStats::non_zero, and Aleph::NTTExact::CoefficientStats::sum.

◆ coeff_to_string()

static std::string Aleph::NTTExact::coeff_to_string ( coeff_type value )

inlinestaticprivate

Definition at line 2478 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp().

◆ conservative_bound()

static coeff_type Aleph::NTTExact::conservative_bound	(	const Array< uint64_t > &	a,
		const Array< uint64_t > &	b
	)

inlinestaticprivate

Definition at line 2516 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Array< T >::is_empty().

◆ exact_modulus_product()

static constexpr coeff_type Aleph::NTTExact::exact_modulus_product ( )

inlinestaticconstexprnoexcept

Product of the three CRT moduli.

Every exact result coefficient must be strictly smaller than this value for the reconstruction to be guaranteed.

Definition at line 2644 of file ntt.H.

◆ exact_modulus_product_impl()

static constexpr coeff_type Aleph::NTTExact::exact_modulus_product_impl ( )

inlinestaticconstexprprivatenoexcept

Definition at line 2413 of file ntt.H.

◆ mul_capped()

static constexpr coeff_type Aleph::NTTExact::mul_capped	(	const coeff_type	lhs,
		const coeff_type	rhs,
		const coeff_type	cap
	)

inlinestaticconstexprprivatenoexcept

Definition at line 2437 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp().

◆ multiply()

static Array< coeff_type > Aleph::NTTExact::multiply	(	const Array< uint64_t > &	a,
		const Array< uint64_t > &	b
	)

inlinestatic

Exact sequential polynomial multiplication.

Parameters

a	First polynomial with non-negative `uint64_t` coefficients.
b	Second polynomial with non-negative `uint64_t` coefficients.

Returns: Exact convolution reconstructed in __uint128_t.

Exceptions

std::invalid_argument if the transform size is unsupported or if the inputs cannot be proven to fit in the CRT reconstruction range.

Definition at line 2673 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Array< T >::is_empty().

Referenced by Aleph::NTT< MOD, ROOT >::bigint_multiply(), main(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ next_power_of_two()

static constexpr size_t Aleph::NTTExact::next_power_of_two ( const size_t n )

inlinestaticconstexprprivatenoexcept

Definition at line 2447 of file ntt.H.

◆ pmultiply()

static Array< coeff_type > Aleph::NTTExact::pmultiply	(	ThreadPool &	pool,
		const Array< uint64_t > &	a,
		const Array< uint64_t > &	b,
		const size_t	chunk_size = `0`
	)

inlinestatic

Exact parallel polynomial multiplication.

Parallelism is applied across the independent prime transforms and then across CRT reconstruction when the supplied pool has more than one worker.

Parameters

pool	Thread pool used for execution.
a	First polynomial with non-negative `uint64_t` coefficients.
b	Second polynomial with non-negative `uint64_t` coefficients.
chunk_size	Reconstruction chunk size (0 selects automatic chunking).

Returns: Exact convolution reconstructed in __uint128_t.

Exceptions

std::invalid_argument if the transform size is unsupported or if the inputs cannot be proven to fit in the CRT reconstruction range.

Definition at line 2704 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::ThreadPool::enqueue(), Aleph::Array< T >::is_empty(), and Aleph::ThreadPool::num_threads().

Referenced by main(), Aleph::NTT< MOD, ROOT >::pbigint_multiply(), and TEST_F().

◆ prime_count()

static constexpr size_t Aleph::NTTExact::prime_count ( )

inlinestaticconstexprnoexcept

Number of CRT primes in the exact multiplier.

Definition at line 2633 of file ntt.H.

◆ prime_supports_product_size()

template<typename PrimeNTT >

static constexpr bool Aleph::NTTExact::prime_supports_product_size ( const size_t required )

inlinestaticconstexprprivatenoexcept

Definition at line 2465 of file ntt.H.

References Aleph::and, and Aleph::divide_and_conquer_partition_dp().

◆ reconstruct_coefficient()

static coeff_type Aleph::NTTExact::reconstruct_coefficient	(	const uint64_t	r0,
		const uint64_t	r1,
		const uint64_t	r2
	)

inlinestaticprivate

Definition at line 2578 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::mod_inv(), and Aleph::mod_mul().

◆ reconstruct_product()

static Array< coeff_type > Aleph::NTTExact::reconstruct_product	(	const Array< uint64_t > &	c0,
		const Array< uint64_t > &	c1,
		const Array< uint64_t > &	c2,
		ThreadPool *const	pool,
		const size_t	chunk_size
	)

inlinestaticprivate

Definition at line 2605 of file ntt.H.

References ah_runtime_error_unless, Aleph::and, Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::ThreadPool::num_threads(), output, and Aleph::parallel_for_index().

◆ sub_mod()

static constexpr uint64_t Aleph::NTTExact::sub_mod	(	const uint64_t	lhs,
		const uint64_t	rhs,
		const uint64_t	mod
	)

inlinestaticconstexprprivatenoexcept

Definition at line 2421 of file ntt.H.

◆ supports_product_size()

static constexpr bool Aleph::NTTExact::supports_product_size ( const size_t required )

inlinestaticconstexprnoexcept

Check whether a target product length is supported.

The length refers to the final convolution length a.size() + b.size() - 1. Each internal prime transform may still use Bluestein or a larger power-of-two staging length.

Definition at line 2656 of file ntt.H.

References Aleph::and, and Aleph::divide_and_conquer_partition_dp().

Referenced by TEST_F().

◆ validate_inputs()

static void Aleph::NTTExact::validate_inputs	(	const Array< uint64_t > &	a,
		const Array< uint64_t > &	b,
		const char *const	ctx
	)

inlinestaticprivate

Definition at line 2555 of file ntt.H.

References ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), and Aleph::Array< T >::size().

Member Data Documentation

◆ primes_

constexpr NTTPrime Aleph::NTTExact::primes_[]

staticconstexprprivate

Initial value:

= {
      {998244353ULL, 3ULL, 23ULL},
      {469762049ULL, 3ULL, 26ULL},
      {1004535809ULL, 3ULL, 21ULL}
    }

Definition at line 2406 of file ntt.H.

The documentation for this class was generated from the following file:

ntt.H

Classes

Public Types

Static Public Member Functions

Private Types

Static Private Member Functions

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ coeff_type

◆ Prime0NTT

◆ Prime1NTT

◆ Prime2NTT

Member Function Documentation

◆ add_capped()

◆ analyze_coefficients()

◆ coeff_to_string()

◆ conservative_bound()

◆ exact_modulus_product()

◆ exact_modulus_product_impl()

◆ mul_capped()

◆ multiply()

◆ next_power_of_two()

◆ pmultiply()

◆ prime_count()

◆ prime_supports_product_size()

◆ reconstruct_coefficient()

◆ reconstruct_product()

◆ sub_mod()

◆ supports_product_size()

◆ validate_inputs()

Member Data Documentation

◆ primes_