On Deterministically Finding an Element of High Order Modulo a Composite
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917004059869184 |
|---|---|
| author | Oznovich, Ziv Volk, Ben Lee |
| author_facet | Oznovich, Ziv Volk, Ben Lee |
| contents | We give a deterministic algorithm that, given a composite number $N$ and a target order $D \ge N^{1/6}$, runs in time $D^{1/2+o(1)}$ and finds either an element $a \in \mathbb{Z}_N^*$ of multiplicative order at least $D$, or a nontrivial factor of $N$. Our algorithm improves upon an algorithm of Hittmeir (arXiv:1608.08766), who designed a similar algorithm under the stronger assumption $D \ge N^{2/5}$. Hittmeir's algorithm played a crucial role in the recent breakthrough deterministic integer factorization algorithms of Hittmeir and Harvey (arXiv:2006.16729, arXiv:2010.05450, arXiv:2105.11105). When $N$ is assumed to have an $r$-power divisor with $r\ge 2$, our algorithm provides the same guarantees assuming $D \ge N^{1/6r}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_07668 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Deterministically Finding an Element of High Order Modulo a Composite Oznovich, Ziv Volk, Ben Lee Data Structures and Algorithms Number Theory We give a deterministic algorithm that, given a composite number $N$ and a target order $D \ge N^{1/6}$, runs in time $D^{1/2+o(1)}$ and finds either an element $a \in \mathbb{Z}_N^*$ of multiplicative order at least $D$, or a nontrivial factor of $N$. Our algorithm improves upon an algorithm of Hittmeir (arXiv:1608.08766), who designed a similar algorithm under the stronger assumption $D \ge N^{2/5}$. Hittmeir's algorithm played a crucial role in the recent breakthrough deterministic integer factorization algorithms of Hittmeir and Harvey (arXiv:2006.16729, arXiv:2010.05450, arXiv:2105.11105). When $N$ is assumed to have an $r$-power divisor with $r\ge 2$, our algorithm provides the same guarantees assuming $D \ge N^{1/6r}$. |
| title | On Deterministically Finding an Element of High Order Modulo a Composite |
| topic | Data Structures and Algorithms Number Theory |
| url | https://arxiv.org/abs/2506.07668 |