#### Document Type

Dissertation

#### Publication Date

5-2022

#### First Advisor

Joshua Holden

#### Abstract

Shor’s algorithm proves that the discrete logarithm problem is in **BQP**. Based on his algorithm, we prove that the primitive root problem, a problem that verifies if some integer *g* is a primitive root modulo *p* where *p* is the largest prime number smaller than *2n* for a given *n*, which is assumed to be harder than the discrete logarithm problem, is in **BQP** by using an oracle quantum Turing machine.

#### Recommended Citation

Wu, Shixin, "The Primitive Root Problem: a Problem in BQP" (2022). *Mathematical Sciences Technical Reports (MSTR)*. 178.

https://scholar.rose-hulman.edu/math_mstr/178

## Comments

Senior Thesis, Department of Mathematics, Rose-Hulman Institute of Technology