pollard_rho.H File Reference

Integer factorization using Pollard's rho algorithm. More...

#include <cstdint>
#include <numeric>
#include <random>
#include <ah-errors.H>
#include <tpl_array.H>
#include <ahSort.H>
#include <primality.H>
#include <modular_arithmetic.H>

Include dependency graph for pollard_rho.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::detail

Functions
uint64_t	Aleph::detail::pollard_rho_step (const uint64_t n, const uint64_t seed, const uint64_t c)
	Inner function for Pollard's rho algorithm.
uint64_t	Aleph::detail::find_any_factor (const uint64_t n)
	Helper to repeatedly apply Pollard's rho until a factor is found.
void	Aleph::detail::extract_prime_factors (const uint64_t n, Array< uint64_t > &factors)
	Recursive extraction of all prime factors.
Array< uint64_t >	Aleph::pollard_rho (uint64_t n)
	Compute the prime factorization of a number using Pollard's rho.

Detailed Description

Integer factorization using Pollard's rho algorithm.

Provides a robust implementation of Pollard's rho algorithm for finding prime factors of 64-bit integers. It includes a random fallback to prevent infinite loops on degenerate cases and uses recursive factor extraction to find all prime factors of a number.

Definition in file pollard_rho.H.