Algorithm | Source Code | Pseudo-Code | Running Time | Memeory Space |
---|---|---|---|---|
Trial Division | C++ | $O({n}^{1/2})$ | $n^{o(1)}$ | |
Fermat Method | C++ | [1, page 226] | between $O(\log n)$ and $O(n)$ depending on the distance between prime factors | $n^{o(1)}$ |
Pollard Rho Method | C++ | [1, page 230] | $O({n}^{1/4})$ (heuristic) | $n^{o(1)}$ |
Polloard Strassen Method2 | C++, Mathematica | [2, Theorem 19.2] | ${n}^{1/4+o(1)}$ | ${n}^{1/4+o(1)}$ |
Dr. Hiary's Method3 | C++(basic), C++(optimal), Mathematica4 | [3, page 2] | ${n}^{1/3+o(1)}$ | $n^{o(1)}$ |
Algorithm | Source Code | Pseudo-Code | Running Time |
---|---|---|---|
Naive Algorithm | C++ | $O(p)$ | |
Baby Step Giant Steps | C++ | [1, page 235] | $O({p}^{1/2})$ |
Pollard Rho Method | C++ | [1, page 232] | $O({p}^{1/4})$ (heuristic) |
[1] Crandall, Richard and Pomerance, Carl. Prime Numbers: A Computational Perspective. New York, NY: Springer, 2005. Internet resource.
[2] Gathen, Joachim and Gerhard, Jürgen. Modern Computer Algebra. Cambridge: Cambridge University Press, 1999. Print.
[3] Hiary, Ghaith. A Deterministic Algorithm for Integer Factorization. Mathematics of Computation. 85.300 (2016). Print.