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 Algorithms¹

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 Jü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.