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}\).