This repository contains an implementation of Pollard's Rho algorithm for prime factorization, alongside a comprehensive theoretical and empirical analysis. The project explores the algorithm's performance through the lens of the Birthday Paradox and Floyd's cycle-finding algorithm.
By running extensive empirical simulations, this project validates the
- Algorithm Implementation: Efficiently finds non-trivial prime factors of composite numbers using pseudo-random walks.
-
Cycle Detection: Utilizes Floyd's "tortoise and hare" cycle-finding approach to detect collisions with
$O(1)$ space complexity. - Empirical Validation: Includes large-scale simulations generating 10-digit prime factors to test collision times and statistical variance.
-
Statistical Analysis: Compares empirical results against theoretical models, proving the robustness of the pseudo-random heuristic (
$f(x) = x^2 + 1$ ).