2025-11-14T23:46:11.547081

On Deterministically Finding an Element of High Order Modulo a Composite

Oznovich, Volk
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}$.
academic

On Deterministically Finding an Element of High Order Modulo a Composite

Basic Information

  • Paper ID: 2506.07668
  • Title: On Deterministically Finding an Element of High Order Modulo a Composite
  • Authors: Ziv Oznovich, Ben Lee Volk (Efi Arazi School of Computer Science, Reichman University, Israel)
  • Classification: cs.DS (Data Structures and Algorithms), math.NT (Number Theory)
  • Submission Date: June 11, 2025 (arXiv v3)
  • Paper Link: https://arxiv.org/abs/2506.07668

Abstract

This paper presents a deterministic algorithm that, given a composite number NN and target order D≥N1/6D \geq N^{1/6}, runs in time D1/2+o(1)D^{1/2+o(1)} and either finds an element a∈ZN∗a \in \mathbb{Z}_N^* with multiplicative order at least DD, or finds a non-trivial factor of NN. The algorithm improves upon Hittmeir's algorithm, which requires the stronger assumption D≥N2/5D \geq N^{2/5}. When NN has an rr-th power factor (r≥2r \geq 2), the algorithm provides the same guarantee under the assumption D≥N1/6rD \geq N^{1/6r}.

Research Background and Motivation

Problem Background

  1. The Challenge of Integer Factorization: Integer factorization is a core problem in computational number theory. The best known randomized algorithms (such as the general number field sieve) have subexponential complexity, while the best deterministic algorithms were strongly exponential until recently.
  2. Importance of Deterministic Algorithms: Although it is theoretically believed that every randomized algorithm can be simulated by a deterministic algorithm with polynomial slowdown, obtaining unconditional derandomization results remains significant in complexity theory and algorithm design.
  3. Role of High-Order Elements: Breakthrough work by Hittmeir and Harvey demonstrated that deterministically finding elements with large multiplicative order is key to designing efficient deterministic factorization algorithms.

Research Motivation

  1. Improving Parameter Range: Hittmeir's algorithm requires D≥N2/5D \geq N^{2/5}, a relatively strict condition that limits the algorithm's applicability.
  2. Enhancing Factorization Algorithms: In the Harvey-Hittmeir factorization algorithm, the step of finding high-order elements runs in time N1/5+o(1)N^{1/5+o(1)}, becoming one of the algorithmic bottlenecks.
  3. Theoretical Significance: Derandomization is an important problem in theoretical computer science, and achieving derandomization in number-theoretic algorithms has profound theoretical implications.

Core Contributions

  1. Parameter Improvement: Reduces the target order requirement from D≥N2/5D \geq N^{2/5} to D≥N1/6D \geq N^{1/6}, significantly extending the algorithm's applicability.
  2. Maintained Runtime: While relaxing parameter requirements, maintains the D1/2+o(1)D^{1/2+o(1)} time complexity.
  3. Optimization for rr-th Power Case: When NN has an rr-th power factor, further reduces the requirement to D≥N1/6rD \geq N^{1/6r}.
  4. Factorization Algorithm Improvement: Provides new factorization subroutines that improve factorization methods with known residue class information.
  5. Theoretical Tools: Establishes tighter bounds on the number of elements in consecutive integers satisfying specific congruence conditions.

Detailed Methodology

Task Definition

Input: Composite number NN and target order D≥N1/6D \geq N^{1/6}Output: Either an element a∈ZN∗a \in \mathbb{Z}_N^* with multiplicative order at least DD, or a non-trivial factor of NNTime Complexity: D1/2+o(1)D^{1/2+o(1)}

Algorithm Architecture

Main Algorithm Structure (Algorithm 4.1)

The algorithm employs an iterative search strategy with the following main steps:

  1. Preprocessing: Check for small factors using Strassen's method
  2. Iterative Search: Search over a=2,3,4,…a = 2, 3, 4, \ldots
  3. Order Computation: Use improved Baby-step Giant-step method
  4. Information Accumulation: Maintain variable MM recording the least common multiple of orders of checked elements
  5. Final Factorization: Use new factorization algorithm when MM is sufficiently large

Core Technical Improvements

1. Improved Bounds on Consecutive Roots (Claim 2.6)

For large integers N, ℓ, if N has a prime factor p > 2ℓ,
then among m = 10√ℓ consecutive integers {a, a+1, ..., a+m},
there exists an element b such that b^ℓ ≢ 1 (mod N)

This improves the search complexity from O(M)O(M) in Hittmeir's algorithm to O(M)O(\sqrt{M}).

2. Residue Class Factorization Algorithm (Theorem 3.2) Given NN and s≥Nαs \geq N^α (α≤1/(4r)α \leq 1/(4r), gcd⁡(N,s)=1\gcd(N,s) = 1), the algorithm finds all rr-th power factors satisfying p≡1(mods)p \equiv 1 \pmod{s} in time N1/(4r)−α+o(1)N^{1/(4r)-α+o(1)}.

Technical Innovation Points

1. Improved Polynomial Construction

Building upon the Harvey-Hittmeir algorithm, the base polynomial is improved from f(x)=x+Pf(x) = x + P to: g(x)=x+s′+s′(P−P~)g(x) = x + s' + s'(P - \tilde{P}) where s′s' is the inverse of ss modulo NN, and P~\tilde{P} is the remainder of PP modulo ss.

2. Search Space Reduction

Using information about prime factors p≡1(mods)p \equiv 1 \pmod{s}, the size of searched roots is reduced from HH to approximately H/sH/s, thereby reducing the number of search intervals by a factor of ss.

3. Application of LLL Lattice Basis Reduction

Construct the polynomial system:

N^{m-\lfloor i/r \rfloor} g(x)^i, & 0 \leq i < rm \\ g(x)^i, & rm \leq i < d \end{cases}$$ Use the LLL algorithm to find short vectors corresponding to polynomials with small coefficients that vanish at the target root. ## Experimental Setup ### Theoretical Analysis Framework This paper primarily conducts theoretical analysis, verifying algorithm correctness and complexity through mathematical proofs: 1. **Correctness Proof**: Proves that the algorithm outputs correct results at each termination point 2. **Complexity Analysis**: Provides detailed analysis of time complexity for each step 3. **Parameter Optimization**: Determines optimal parameter settings through theoretical analysis ### Key Lemma Verification - **Lemma 2.5** (Forbes et al.): Bounds on the number of roots of polynomial systems - **Claim 2.6**: Existence of elements in consecutive integers not satisfying congruence conditions - **Claim 3.3**: Bounds on root sizes under residue class constraints ## Experimental Results ### Theoretical Results 1. **Main Theorem (Theorem 1.1)**: - Parameter requirement: $D \geq N^{1/6}$ (vs. Hittmeir's $N^{2/5}$) - Runtime: $D^{1/2+o(1)}$ (unchanged) 2. **$r$-th Power Case (Theorem 4.2)**: - Parameter requirement: $D \geq N^{1/6r}$ - Runtime: $D^{1/2+o(1)}$ 3. **Factorization Algorithm (Theorem 3.2)**: - Condition: $s \geq N^α$, $α \leq 1/(4r)$ - Runtime: $N^{1/(4r)-α+o(1)}$ ### Complexity Improvements - **Search Steps**: Improved from $O(M)$ to $O(\sqrt{M})$ - **Parameter Range**: Exponent reduced from $2/5$ to $1/6$ - **Factorization Efficiency**: Significantly enhanced with known residue information ### Comparison with Related Work | Algorithm | Parameter Requirement | Runtime | Year | |-----------|----------------------|---------|------| | Hittmeir | $D \geq N^{2/5}$ | $D^{1/2+o(1)}$ | 2018 | | GFHP | $D \geq N^{1/4r}$ | $D^{1/2+o(1)}$ | 2025 | | This Work | $D \geq N^{1/6}$ | $D^{1/2+o(1)}$ | 2025 | ## Related Work ### Development of Deterministic Factorization Algorithms 1. **Classical Methods**: Pollard-Strassen algorithm ($N^{1/4+o(1)}$) 2. **Recent Breakthroughs**: Hittmeir-Harvey algorithm ($N^{1/5+o(1)}$) 3. **Randomized Algorithms**: Subexponential algorithms such as the general number field sieve ### Finding High-Order Elements 1. **Randomized Approaches**: Random elements typically have large order 2. **Deterministic Challenges**: How to deterministically find such elements 3. **Applications**: Critical role in factorization algorithms ### Applications of Lattice Basis Reduction 1. **Coppersmith's Method**: Finding small roots of polynomials 2. **Harvey-Hittmeir**: Factorization of $r$-th power divisors 3. **This Work's Extension**: Improvements combining residue class information ## Conclusions and Discussion ### Main Conclusions 1. Successfully reduces the parameter requirement for finding high-order elements from $N^{2/5}$ to $N^{1/6}$ 2. Maintains the optimal runtime of $D^{1/2+o(1)}$ 3. Provides improved subroutines for deterministic factorization algorithms ### Limitations 1. **Prime Case**: The algorithm may not produce useful output for prime inputs 2. **Parameter Constraints**: Still requires the lower bound $D \geq N^{1/6}$ 3. **Practical Efficiency**: The practical effectiveness of theoretical improvements requires verification ### Future Directions 1. **Breaking the 1/5 Barrier**: Applying this algorithm in factorization algorithms may yield further improvements 2. **Prime Field Generators**: Deterministically finding generators of $\mathbb{Z}_p^*$ 3. **Discrete Logarithm**: Improving deterministic discrete logarithm algorithms ## In-Depth Evaluation ### Strengths 1. **Theoretical Innovation**: Cleverly combines multiple mathematical tools to achieve significant parameter improvements 2. **Technical Depth**: Extensions of the Harvey-Hittmeir algorithm demonstrate substantial technical expertise 3. **Practical Value**: Provides better building blocks for deterministic factorization algorithms 4. **Rigorous Proofs**: Mathematical reasoning is sound with detailed complexity analysis ### Weaknesses 1. **Experimental Verification**: Lacks actual implementation and performance testing 2. **Constant Factors**: The $o(1)$ terms may be non-negligible in practice 3. **Limited Scope**: Handling of special cases (such as primes) is limited ### Impact 1. **Theoretical Contribution**: Advances the development of deterministic number-theoretic algorithms 2. **Methodological Value**: Techniques provided may apply to other related problems 3. **Foundation for Future Work**: Establishes basis for further improvements in factorization algorithms ### Applicable Scenarios 1. **Theoretical Research**: Complexity theory and algorithm design 2. **Cryptography**: Security applications requiring deterministic guarantees 3. **Number-Theoretic Computation**: Mathematical computations involving large integers ## References - [Hit18] Markus Hittmeir. A babystep-giantstep method for faster deterministic integer factorization - [Har21] David Harvey. An exponent one-fifth algorithm for deterministic integer factorisation - [HH22b] David Harvey and Markus Hittmeir. A log-log speedup for exponent one-fifth deterministic integer factorisation - [GFHP25] Yiming Gao, Yansong Feng, Honggang Hu, and Yanbin Pan. On factoring and power divisor problems via rank-3 lattices --- This paper makes important contributions to the field of deterministic number-theoretic algorithms, achieving significant parameter improvements through clever technical innovations and providing valuable tools and insights for future research.