{"id":"arxiv/2605.09592","url":"https://arxiv.org/abs/2605.09592","tags":["cs.DS","cs.DM","math.NT"],"score":0,"title":"Deterministically finding an element of large order in $\\mathbb{Z}_N^*$","domain":"cs.DS","source":"arxiv","authors":["Itamar Nir"],"reviews":0,"subject":"cs.DS","summary":"In this paper, we present an improvement for the problem of deterministically finding an element of large multiplicative order modulo some integer $N$. This problem arises as a key subroutine in current deterministic factoring algorithms, such as those proposed by Harvey and Hittmeir [Mathematics of Computation, 2021]. Specifically, let $D \\exp\\left(\\sqrt{2\\log N \\log \\log N}\\right). \\end{equation} We give a deterministic algorithm that does one of the following: Returns an element $a \\in \\mathbb{Z}_N^*$ with $\\operatorname{ord}_N(a) > D$; Returns a non-trivial factor of $N$; Or reports that…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-10","reactions":{}}