On Deterministically Finding an Element of High Order Modulo a Composite

2025/06/09 by Ziv Oznovich, Oznovich, Ziv, Ben Lee Volk +1 · 1 citation
Computer Science · Mathematics · #Analytic Number Theory Research #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2506.07668

openalex publication_date 2025/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a deterministic algorithm that, given a composite number N and a target order D ≥ N^1/6, runs in time D^1/2+o(1) and finds either an element a ∈ ℤ_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 ≥ 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≥ 2, our algorithm provides the same guarantees assuming D ≥ N^1/6r.

Cited by

• On Factoring and Power Divisor Problems via Rank-3 Lattices and the Second Vector

Related

• Note Integer Factoring Methods III
• Deterministic Integer Factorization Algorithms
• An exponent one-fifth algorithm for deterministic integer factorisation
• Deterministic polynomial factorisation modulo many primes
• A deterministic algorithm for integer factorization