On Deterministically Finding an Element of High Order Modulo a Composite

Ziv Oznovich, Ben Lee Volk

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 $a \in \mathbb{Z}_N…