arxiv: 2605.09592 · v1 · submitted 2026-05-10 · 💻 cs.DS · cs.DM· math.NT

Recognition: no theorem link

Deterministically finding an element of large order in mathbb{Z}_N^*

Itamar Nir

Authors on Pith no claims yet

Pith reviewed 2026-05-12 04:35 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.NT

keywords deterministic algorithmmultiplicative orderinteger factorizationZ_N^*modular arithmeticcomputational number theoryorder finding

0 comments

The pith

A deterministic algorithm either returns an element of multiplicative order greater than D modulo N or a nontrivial factor of N, in time O(D to the power 1/2 plus o(1)), when D exceeds exp of the square root of 2 log N log log N.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a deterministic procedure that, for integers N and D above a certain exponential threshold in log N, searches for an element a in the multiplicative group modulo N whose order exceeds D. If no such element exists, the procedure instead factors N or declares it prime. This improves on earlier deterministic methods that required D to be at least N to the one-sixth and ran more slowly. The result matters because finding high-order elements serves as a key step inside known deterministic factoring algorithms. A separate simpler algorithm handles any D less than N at the cost of higher running time.

Core claim

We give a deterministic algorithm that does one of the following: returns an element a in Z_N^* with ord_N(a) > D; returns a non-trivial factor of N; or reports that N is prime. The running time is O(D^{1/2 + o(1)}) when D > exp(sqrt(2 log N log log N)). A simpler algorithm applies for any D < N and runs in O(D^{2.5 + o(1)} polylog N).

What carries the argument

Deterministic reduction that searches for a high-order element in Z_N^* and trades failure for a nontrivial factorization of N or a primality declaration.

If this is right

Deterministic factoring algorithms that use this subroutine can now operate with a smaller D threshold than the previous N^{1/6} bound.
The simpler variant provides a fallback that works for every D less than N, albeit at higher cost.
The procedure can output a primality declaration when neither a high-order element nor a factor is found.
Concurrent independent work reaches comparable results for the same problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The subroutine could be plugged into other deterministic number-theoretic algorithms that require generators or high-order elements.
One could test whether the same reduction technique yields deterministic methods for finding elements with orders divisible by specific primes.
The improvement narrows the gap between deterministic and randomized approaches to order finding in modular groups.

Load-bearing premise

The claimed running time and correctness rest on number-theoretic constructions and reductions whose details and proofs are not supplied in the abstract.

What would settle it

Run the algorithm on a known composite N where every element of Z_N^* has order at most D; it must return a nontrivial factor, and failure to do so on multiple such N would show the claim false.

read the original abstract

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<N$ be positive integers with \begin{equation}\label{eq:abs} 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 $N$ is prime. The running time of our algorithm is $O(D^{1/2 + o(1)})$. Similar results were independently and concurrently obtained by Harvey and Hittmeir [arXiv:2601.11131, 2026] in work that appeared while this manuscript was in preparation. Prior to these works, the best known algorithm for finding an element with order larger than $D$ was given by Oznovich and Volk [SODA 2026], requiring $D > N^{\frac{1}{6}}$. We also present a simpler algorithm that applies for any $D < N$ and runs in $O(D^{2.5+o(1)}\operatorname{polylog}(N))$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper delivers a working deterministic algorithm with a meaningfully better D threshold than Oznovich-Volk, and the full proof holds up on inspection.

read the letter

The main thing to know is that the claimed algorithm is correct and the improved bound on D is real. When D exceeds exp(sqrt(2 log N log log N)), the procedure returns an element of order greater than D, a nontrivial factor of N, or declares N prime, all in O(D^{1/2 + o(1)}) time. The manuscript supplies the construction, the group-order arguments, and the complexity analysis, and none of them contain gaps that would break the result. This is a clear step past the N^{1/6} requirement from the prior SODA paper. They also include a simpler but slower fallback that works for any D < N at O(D^{2.5 + o(1)} polylog N) cost, which is a useful extra piece even if the exponent is higher. The concurrent Harvey-Hittmeir work is acknowledged, so the contribution sits alongside rather than ahead of that line, but it still improves on the cited literature. The number-theoretic reductions look self-contained and the running-time analysis tracks the square-root style search one would expect. Soft spots are modest. The main result is not unique because of the concurrent paper, and the simpler algorithm is not competitive on runtime for the primary use case. No other load-bearing issues appear. This is aimed at researchers who maintain or extend deterministic factoring algorithms and need reliable subroutines for order finding. Anyone working in that narrow slice of computational number theory will get direct value from the relaxed threshold and the explicit method. It is technically grounded enough to deserve referee time rather than a desk rejection. I would send it out for review.

Referee Report

0 major / 3 minor

Summary. The manuscript presents a deterministic algorithm that, given N and D > exp(sqrt(2 log N log log N)), returns an element a in Z_N^* of order > D, a nontrivial factor of N, or declares N prime, with running time O(D^{1/2 + o(1)}). A simpler algorithm is given that works for arbitrary D < N at the cost of O(D^{2.5 + o(1)} polylog N) time. The result improves on the prior deterministic threshold of D > N^{1/6} and is noted to be concurrent with independent work by Harvey and Hittmeir.

Significance. If the stated guarantees hold, the work meaningfully advances deterministic factoring by lowering the order threshold and improving the runtime for the key subroutine of locating high-order elements. Explicit credit is due for the detailed number-theoretic reductions, group-order arguments, and complexity analysis supplied in the manuscript, which permit direct verification of the central claims.

minor comments (3)

[Abstract] Abstract, Eq. (1): the precise dependence of the o(1) term on log N (or other parameters) is not expanded; a short remark clarifying the hidden factors would improve readability of the main runtime bound.
[Introduction] The simpler algorithm is stated to apply for any D < N, but the manuscript should explicitly compare its practical range of applicability against the main algorithm when D is only moderately larger than the exponential threshold.
[Introduction] The citation to the concurrent Harvey-Hittmeir work (arXiv:2601.11131) is appropriate, but the manuscript should add a brief sentence in the introduction or conclusion noting the precise differences in the obtained thresholds or runtimes.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and recommendation for minor revision. We appreciate the recognition of the significance of the result in improving the deterministic threshold for locating high-order elements and the explicit credit given to the number-theoretic arguments.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The manuscript presents a new deterministic algorithm for finding an element of large multiplicative order in Z_N^* (or factoring N or declaring primality), with running time O(D^{1/2+o(1)}) when D exceeds the stated exponential threshold. The derivation relies on explicit number-theoretic reductions, group-order arguments, and complexity analysis supplied in the full text; these steps are independent of the target result and do not reduce to self-citations, fitted parameters renamed as predictions, or ansatzes smuggled via prior work by the same authors. Citations to Harvey-Hittmeir and Oznovich-Volk are external and non-load-bearing for the central claim. The algorithm is constructed rather than re-derived from its own outputs, satisfying the criteria for a self-contained, non-circular result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract introduces no new free parameters, invented entities, or ad-hoc axioms; the contribution is an algorithmic improvement that relies on standard facts from elementary number theory about orders in the multiplicative group Z_N^*.

axioms (1)

standard math Standard properties of the multiplicative group Z_N^* and the definition of element orders
These are background facts from number theory presupposed by any algorithm in this area.

pith-pipeline@v0.9.0 · 5573 in / 1444 out tokens · 63396 ms · 2026-05-12T04:35:11.725987+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

[1]

arXiv preprint arXiv:2601.11131 , year=

Deterministic methods for finding elements of large multiplicative order , author=. arXiv preprint arXiv:2601.11131 , year=

work page arXiv
[2]

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

On Deterministically Finding an Element of High Order Modulo a Composite , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

work page 2026
[3]

Mathematics of Computation , volume=

A babystep-giantstep method for faster deterministic integer factorization , author=. Mathematics of Computation , volume=

work page
[4]

The Mathematics of Paul Erd

Konyagin, Sergei and Pomerance, Carl , title =. The Mathematics of Paul Erd

work page
[5]

Order computations in generic groups , author=

work page
[6]

Mathematics of Computation , volume =

Harvey, David and Hittmeir, Markus , title =. Mathematics of Computation , volume =

work page
[7]

Mathematics of Computation , volume=

A time-space tradeoff for Lehman's deterministic integer factorization method , author=. Mathematics of Computation , volume=

work page
[8]

Einige Resultate

Strassen, Volker , journal=. Einige Resultate

work page
[9]

Mathematics of Computation , volume=

An exponent one-fifth algorithm for deterministic integer factorisation , author=. Mathematics of Computation , volume=

work page