Deterministically finding an element of large order in $\mathbb{Z}_N^*$
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.09592
curl -X POST /api/v1/records/arxiv/2605.09592/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.09592/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'