{"id":"arxiv/2601.11131","url":"https://arxiv.org/abs/2601.11131","tags":["math.NT"],"score":0,"title":"Deterministic methods for finding elements of large multiplicative order","domain":"math.NT","source":"arxiv","authors":["David Harvey","Markus Hittmeir"],"reviews":0,"subject":"math.NT","summary":"We revisit the problem of rigorously and deterministically finding elements of large order in the multiplicative group of integers modulo a natural number $N$. Solving this problem is an essential step in several recent deterministic algorithms for factoring $N$, including the currently fastest ones. In 2018, the second author gave an algorithm that for a given target order $D \\geq N^{2/5}$, finds either an element of order exceeding $D$, or a nontrivial divisor of $N$, or proves that $N$ is prime. The running time was \\[ O\\left(\\frac{D^{1/2}}{(\\log \\log D)^{1/2}} \\log^2 N \\right) \\] bit…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-16","reactions":{}}