Ziv Oznovich

On Deterministically Finding an Element of High Order Modulo a Composite

2026 · Society for Industrial and Applied Mathematics eBooks

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 …