prime_test.cpp File Reference

Primary module interface unit for module prime_test. More...

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <optional>
#include <type_traits>
import modulo;
import mod_int;
import lucas_sequence;
import int128;
import base;

Include dependency graph for prime_test.cpp:

Functions
template<Integer T, std::ranges::input_range R> requires std::convertible_to<std::ranges::range_value_t<R>, T>
constexpr std::optional< bool >	ntlib::is_prime_trial_division (T n, R &&list) noexcept
	Uses trial division to test whether a given number is prime relative to a given precomputed list of primes.
template<Integer T>
constexpr bool	ntlib::miller_selfridge_rabin_test (T n, T a) noexcept
	Miller-Selfridge-Rabin primality test.
constexpr bool	ntlib::forisek_jancina_no_base_cases (uint32_t n) noexcept
	Subroutine for optimized prime test for a given 32-bit integer.
constexpr bool	ntlib::is_prime_32 (uint32_t n) noexcept
	Deterministic prime test optimized for a given 32-bit integer.
constexpr bool	ntlib::is_prime_64 (uint64_t n) noexcept
	Deterministic prime test optimized for a given 64-bit integer.
template<Integer T>
constexpr bool	ntlib::is_strong_lucas_probable_prime (T n) noexcept
	Checks whether a given number is a Lucas probable prime.
template<Integer T>
constexpr bool	ntlib::is_prime_baillie_psw (T n) noexcept
	Baillie-PSW (probable) prime test.
template<Integer T>
constexpr bool	ntlib::is_prime (T n) noexcept
	Prime test.

Detailed Description

Primary module interface unit for module prime_test.

Function Documentation

forisek_jancina_no_base_cases()

bool ntlib::forisek_jancina_no_base_cases ( uint32_t n )

nodiscardconstexprnoexcept

Subroutine for optimized prime test for a given 32-bit integer.

Based on hashing and Miller-Selfridge-Rabin. See: https://ceur-ws.org/Vol-1326/020-Forisek.pdf

Does not check bases cases (numbers divisible by 2, 3, 5, 7)!

Parameters

n	The given number.

Returns

Whether \(n\) is prime.

is_prime()

template<Integer T>

bool ntlib::is_prime ( T n )

nodiscardconstexprexportnoexcept

Prime test.

Deterministic for all integers \(n \leq 2^64\). Probabilistic for larger values. Use this function template whenever there is no strong reason to use any other.

Template Parameters

T	An integer-like type.

Parameters

n	The number to test for primality.

Returns

Whether \(n\) is prime.

is_prime_32()

bool ntlib::is_prime_32 ( uint32_t n )

nodiscardconstexprnoexcept

Deterministic prime test optimized for a given 32-bit integer.

Correct if the given number is at most \(2^32 - 1\).

Parameters

n	The given number.

Returns

Whether \(n\) is prime.

is_prime_64()

bool ntlib::is_prime_64 ( uint64_t n )

nodiscardconstexprnoexcept

Deterministic prime test optimized for a given 64-bit integer.

Correct if the given number is at most \(2^64 - 1\).

Parameters

n	The given number.

Returns

Whether \(n\) is prime.

is_prime_baillie_psw()

template<Integer T>

bool ntlib::is_prime_baillie_psw ( T n )

nodiscardconstexprexportnoexcept

Baillie-PSW (probable) prime test.

Deterministic for all integers \(n \leq 2^64\).

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns

Whether \(n\) is a prime number.

is_prime_trial_division()

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

std::optional< bool > ntlib::is_prime_trial_division ( T n, R && list )

nodiscardconstexprexportnoexcept

Uses trial division to test whether a given number is prime relative to a given precomputed list of primes.

Assumes that the given list of primes is sorted and contains no gaps. If \(p\) is the largest prime in the given list, then the primality of all numbers up to \(p^2\) can be determined correctly. For greater numbers, no decision is made.

Template Parameters

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

Parameters

n	The given number.
list	The given list of primes.

Return values

std::optional<bool>{true}	If the number is prime.
std::optional<bool>{false}	If the number is composite.
std::nullopt	If primality could not be determined by the given list of primes.

is_strong_lucas_probable_prime()

template<Integer T>

bool ntlib::is_strong_lucas_probable_prime ( T n )

nodiscardconstexprexportnoexcept

Checks whether a given number is a Lucas probable prime.

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns

Whether the given number is a strong Lucas probable prime.

miller_selfridge_rabin_test()

template<Integer T>

bool ntlib::miller_selfridge_rabin_test ( T n, T a )

nodiscardconstexprexportnoexcept

Miller-Selfridge-Rabin primality test.

Given an odd integer \(n > 2\), tests if \(n\) is a strong propable prime with respect to a given base.

Template Parameters

T	An integer-like type.

Parameters

n	The given number. Must be odd and greater than \(2\)
a	The given base.

Returns

Whether \(n\) is a strong probable prime with respect to base \(a\).