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 \geq N^{1/6}\) , runs in time \(D^{1/2+0(1)}\) and finds either an element \(a \in \mathbb{Z}_N^*\) of multiplicative order at least \({D}\) , or a nontrivial factor of \({N}\) . Our algorithm improves upon an algorithm of Hittmeir [14], who designed a similar algorithm under the stronger assumption \(D \geq N^{2/5}\) . Hittmeir's algorithm played a crucial role in the recent breakthrough deterministic integer factorization algorithms of Hittmeir and Harvey [10, 12, 15]. When \({N}\) is assumed to have an \(r \geq 2\) -power divisor with \(\) , our algorithm provides the same guarantees assuming \(D \geq N^{\frac{1}{6r}}\) .