Implementations of Algorithms in Number Theory

• Created by: Lillian Zeng; Advisor: Dr. Ghaith A. Hiary
• All of the following implementations used GNU MP Bignum Library to do arithmetic on very large numbers.
• The following implementations for integer factorization algorithms find the least prime factor for an integer $n$.
• Integer Factorization Algorithms1
Algorithm Source Code Pseudo-Code Running Time
Trial Division C++ $O({n}^{1/2})$
Fermat Method C++ [1, page 226] between $O({n}^{1/2})$ and $O(n)$ depending on the distance between prime factors
Pollard Rho Method C++ [1, page 230] $O({n}^{1/4})$ (heuristic)
Dr. Hiary's Method 2 C++(basic), C++(optimal), Mathematica3 [3, page 2] ${n}^{1/3+o(1)}$
• The following implementations for discrete logarithm algorithms solve the discrete log problem in a group. I have implemented those algorithms for the group $(\mathbb{Z}/p\mathbb{Z})^*$, where $p$ is a prime number.
• Discrete Logarithm Algorithms
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. Poster for 2017 OSU Denman Research Forum - "Elementary Algorithms in Number Theory" here

2. Poster for 2016 OSU Summer Research Forum - "Using C++ programming to implement a deterministic algorithm for integer factorization" here

3. This code was written by Dr. Hiary

References

[1] Crandall, Richard E, and Carl Pomerance. Prime Numbers: A Computational Perspective. New York, NY: Springer, 2005. Internet resource.

[2] Gathen, Joachim , and JuÌˆrgen Gerhard. Modern Computer Algebra. Cambridge: Cambridge University Press, 1999. Print.

[3] Hiary, Ghaith A. A Deterministic Algorithm for Integer Factorization. Mathematics of Computation. 85.300 (2016). Print.