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 ≥ N1/6\) , runs in time \(D1/2+0(1)\) and finds either an element \(a ∈ 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 ≥ N2/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 ≥ 2\) -power divisor with \(\) , our algorithm provides the same guarantees assuming \(D ≥ N1/6r\) .