Deterministic methods for finding elements of large multiplicative order
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.11131
curl -X POST /api/v1/records/arxiv/2601.11131/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.11131/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'