On Deterministically Finding an Element of High Order Modulo a Composite

We give a deterministic algorithm that, given a composite number $N$ and a target order $D \ge N^{1/6}$, runs in time $D^{1/2+o(1)}$ and finds either an element $c \in \mathbb{Z}_N^{\ast}$ of multiplicative order at least $D$, or a nontrivial factor of $N$. Our algorithm improves upon an algorithm of Hittmeir (Math. Comp., 2018), who designed a similar algorithm under the stronger assumption $D \ge N^{2/5}$. Hittmeir's algorithm played a crucial role in the recent breakthrough deterministic integer factorization algorithms of Hittmeir and Harvey (Math. Comp., 2021; Math. Comp., 2021; Math. Comp., 2022). When $N$ is assumed to have an $r$-power divisor with $r \ge 2$, our algorithm provides the same guarantees assuming $D \ge N^{1/6r}$.