Deterministically finding an element of large order in $\mathbb{Z}_N^*$
This provides a faster deterministic subroutine for factoring algorithms, benefiting computational number theory researchers.
The paper improves deterministic algorithms for finding an element of large multiplicative order modulo N, a key subroutine in factoring algorithms. The main algorithm runs in O(D^{1/2+o(1)}) time for D > exp(sqrt(2 log N log log N)), significantly improving over prior work requiring D > N^{1/6}.
In this paper, we present an improvement for the problem of deterministically finding an element of large multiplicative order modulo some integer $N$. This problem arises as a key subroutine in current deterministic factoring algorithms, such as those proposed by Harvey and Hittmeir [Mathematics of Computation, 2021]. Specifically, let $D<N$ be positive integers with \begin{equation}\label{eq:abs} D > \exp\left(\sqrt{2\log N \log \log N}\right). \end{equation} We give a deterministic algorithm that does one of the following: Returns an element $a \in \mathbb{Z}_N^*$ with $\operatorname{ord}_N(a) > D$; Returns a non-trivial factor of $N$; Or reports that $N$ is prime. The running time of our algorithm is $O(D^{1/2 + o(1)})$. Similar results were independently and concurrently obtained by Harvey and Hittmeir [arXiv:2601.11131, 2026] in work that appeared while this manuscript was in preparation. Prior to these works, the best known algorithm for finding an element with order larger than $D$ was given by Oznovich and Volk [SODA 2026], requiring $D > N^{\frac{1}{6}}$. We also present a simpler algorithm that applies for any $D < N$ and runs in $O(D^{2.5+o(1)}\operatorname{polylog}(N))$.