prime_decomposition.cpp File Reference

Primary module interface unit for module prime_decomposition. More...

#include <cassert>
#include <cstddef>
#include <cstdlib>
#include <concepts>
#include <limits>
#include <optional>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>
#include "prime_list.hpp"
import prime_test;
import prime_generation;
import int128;
import base;

Include dependency graph for prime_decomposition.cpp:

Classes
struct	ntlib::prime_power< T >
	Represents a single prime power. More...

Typedefs
template<Integer T>
using	ntlib::prime_factors = std::vector<prime_power<T>>
	Represents a prime factorization.

Functions
template<Integer T, std::ranges::input_range R> requires std::convertible_to<std::ranges::range_value_t<R>, T>
constexpr std::pair< prime_factors< T >, T >	ntlib::prime_decomposition_list_remainder (T n, R &&list)
	Computes a prime decomposition of a given number using a provided list of potential prime divisors.
template<Integer T, std::ranges::input_range R> requires std::convertible_to<std::ranges::range_value_t<R>, T>
constexpr prime_factors< T >	ntlib::prime_decomposition_list (T n, R &&list)
	Computes a prime decomposition of a given number using a provided list of potential prime divisors.
template<Integer T>
constexpr prime_factors< T >	ntlib::prime_decomposition_32 (T n)
	Computes the prime decomposition of a number up to \(2^32 - 1\).
template<Integer T, std::invocable< T > F>
constexpr std::optional< T >	ntlib::find_factor_pollard_rho_mult (T n, F f, T x, const std::size_t MULTIPLICATIONS=128) noexcept
	Finds a factor using Pollard's rho algorithm.
template<Integer T>
constexpr T	ntlib::find_factor (T n) noexcept
	Finds a non-trivial factor of a given composite number.
template<Integer T>
constexpr prime_factors< T >	ntlib::prime_decomposition_large (T n)
	Decompose a given number into its prime decomposition.
template<Integer T>
constexpr prime_factors< T >	ntlib::prime_decomposition (T n)
	Computes the prime decomposition of a given number.

Detailed Description

Primary module interface unit for module prime_decomposition.

Typedef Documentation

prime_factors

template<Integer T>

using ntlib::prime_factors = std::vector<prime_power<T>>

export

Represents a prime factorization.

Template Parameters

T	An integer-like type.

Function Documentation

find_factor()

template<Integer T>

T ntlib::find_factor ( T n )

nodiscardconstexprexportnoexcept

Finds a non-trivial factor of a given composite number.

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns

A non-trivial factor.

find_factor_pollard_rho_mult()

template<Integer T, std::invocable< T > F>

std::optional< T > ntlib::find_factor_pollard_rho_mult ( T n, F f, T x, const std::size_t MULTIPLICATIONS = 128 )

nodiscardconstexprnoexcept

Finds a factor using Pollard's rho algorithm.

Given an odd composite number \(n\), this function template tries to find a non-trivial (possibly non-prime) factor of \(n\) using Pollard's rho algorithm. Cycles are detected using Floyd's algorithm.

Template Parameters

T	An integer-like type.
F	A function object.

Parameters

n	The odd composite.
f	A polynomial function to generate a "pseudorandom" sequence. A usual choice for the polynomial function \(f\) would be: \(f(x) = (x^2 + 1) \mod n\).
x	Initial value for parameter \(x\).
MULTIPLICATIONS	The number of multiplications to do instead of expensive gcd-calls.

Returns

A std::optional<T> that is either empty or contains a non-trivial factor.

prime_decomposition()

template<Integer T>

prime_factors< T > ntlib::prime_decomposition ( T n )

nodiscardconstexprexport

Computes the prime decomposition of a given number.

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns

A vector of prime powers.

prime_decomposition_32()

template<Integer T>

prime_factors< T > ntlib::prime_decomposition_32 ( T n )

nodiscardconstexpr

Computes the prime decomposition of a number up to \(2^32 - 1\).

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns

A vector of prime powers.

prime_decomposition_large()

template<Integer T>

prime_factors< T > ntlib::prime_decomposition_large ( T n )

nodiscardconstexpr

Decompose a given number into its prime decomposition.

Does not use trial division to find small prime factors, so this function should only be calles for numbers that do not have small prime factors.

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns

A prime decomposition.

prime_decomposition_list()

template<Integer T, std::ranges::input_range R>
requires std::convertible_to<std::ranges::range_value_t<R>, T>

prime_factors< T > ntlib::prime_decomposition_list ( T n, R && list )

nodiscardconstexprexport

Computes a prime decomposition of a given number using a provided list of potential prime divisors.

The remainder (the largest divisor coprime to all potential prime divisors) will be appended to the prime decomposition with an exponent of \(1\).

Note

When the list of potential prime divisors contains all primes up to \(\lfloor\sqrt{n}\rfloor\), then the return value is the correct prime decomposition.

Template Parameters

T	An integer-like type.
R	An input-range.

Parameters

n	The number to decompose.
list	The list of potential prime divisors.

Returns

A prime decompositon of.

prime_decomposition_list_remainder()

template<Integer T, std::ranges::input_range R>
requires std::convertible_to<std::ranges::range_value_t<R>, T>

std::pair< prime_factors< T >, T > ntlib::prime_decomposition_list_remainder ( T n, R && list )

nodiscardconstexpr

Computes a prime decomposition of a given number using a provided list of potential prime divisors.

The remainder (the largest divisor coprime to all potential prime divisors) will be returned seperately.

Template Parameters

T	An integer-like type.
R	An input-range.

Parameters

n	The given number.
list	The list of potential prime divisors. Must be sorted and contain all primes up to some upper bound.

Returns

A std::pair containing a list of prime powers dividing n as its first element and the remainder (coprime with all primes in list) as its second element.