On Deterministically Finding an Element
of High Order Modulo a Composite

Ziv Oznovich and Ben Lee Volk

Reichman University

Integer Factorization

  • Given a positive integer $N$, find its prime factorization
    • \( N = p_1^{e_1} \cdot p_2^{e_2} \cdot \dots \cdot p_k^{e_k} \)
    • $p_i$'s are prime integers
    • $e_i$'s are positive integers
  • Note that the input size is \( O(\log N) \)

Motivation

  • Fundamental problem in computational number theory
  • RSA encryption relies on the hardness of factoring $N = pq$
  • Derandomization is believed to be possible with only polynomial slowdown, but
    • Fastest randomized algorithm runs in $\exp(\tilde{O}(\sqrt{\log N}))$ (Dixon 81 and Pomerance 81)
    • Fastest deterministic algorithms (Deterministic, rigorously proven)
      • Trial division - $N^{1/2}$
      • Lehman 74 - $N^{1/3}$
      • Strassen 77 and Pollard 74 - $N^{1/4}$
      • Hittmeir 20 - $N^{2/9}$
      • Harvey 21 - $N^{1/5}$

The Role of Multiplicative Order in Factorization

  • Latest factorization algorithm relies on finding such an element
    • They specifically require finding an element whose order is at least $N^{1/5}$
    • Such an element doesn't necessarily exist (but then it’s easy to factor $N$)
  • Even when most elements in $\mathbb{Z}_N^*$ have large order, it is unclear how to find one deterministically

Definitions

  • $\mathbb{Z}_N^*$ – Multiplicative Group of Integers Modulo $N$
    • Consists of all integers $a$ such that $1 \le a < N$ and $\gcd(a, N) = 1$
  • $\mathrm{ord}_N(a)$ – Order of an Element $a$ Modulo $N$
    • The smallest positive integer $k$ such that $a^k \equiv 1 \pmod{N}$
    • Example (for $a = 2$, $N = 15$): $2^1 = 2$, $2^2 = 4$, $2^3 = 8$, $2^4 = 16 \equiv 1 \pmod{15}$
    • So $\mathrm{ord}_{15}(2) = 4$

Previous Work: Hittmeir’s Algorithm

  • Given integers \(N\) and \(D \ge N^{2/5}\)
  • Outputs
    • an element $a \in \mathbb{Z}_N^*$ of multiplicative order at least \(D\)
    • or a non‑trivial factor of \(N\)
    • As a subroutine in a factorization algorithm this is a “win‑win” result
  • Runs in time \(D^{1/2}\)
  • Large-order elements may not always exist

Our Result

  • We improve Hittmeir’s algorithm
  • Our algorithm runs in time $D^{1/2}$
  • It works for a wider range of parameters namely $D \ge N^{1/6}$
    • Compared to $D \ge N^{2/5}$
  • This enables finding an element of order $N^{1/5}$ in $N^{1/10}$ time
    • Compared to finding an element of order $N^{2/5}$ in $N^{1/5}$ time

Main Algorithm (Simplified)

  • Input: Integers $N$ and $D$
  • Output: Element $a \in \mathbb{Z}_N^*$ such that $\mathrm{ord}_N(a) \ge D$ or a factor of $N$
  • Let $M= \mathrm{lcm} $ of all orders encountered so far
  • Try $a = 2, 3, 4, \dots$
    • While $a^M \equiv 1\pmod N$ continue to next $a$
    • If $\mathrm{ord}_N(a) > D$ return $a$
    • $M\coloneqq \mathrm{lcm}(M, \mathrm{ord}_N(a))$
    • [Details Omitted...]
    • Until $M \geq D$
      • Factor $N$

Consecutive Roots

  • "While $a^M \equiv 1\pmod N$ continue to next $a$"
  • How many consecutive $a$'s can satisfy $a^M \equiv 1\pmod N$?
  • Hittmeir's approach
    • If $a^M \equiv 1\pmod N$ then $a^M \equiv 1\pmod p$ for each prime factor $p$ of $N$
    • $x^M-1$ has at most $M$ roots over $\mathbb{Z}^*_p$
    • So the number of consecutive $a$'s are at most $M$
  • We improve this bound to $O(M^{1/2})$

Shanks' Method

  • Goal: If $\operatorname{ord}_N(a) < D$ calculate it, otherwise, state that it is larger than $D$
  • Closely related to discrete-log problem
  • Shanks' Baby-Step Giant-Step algorithm (Shanks 71):
    • $a^k\equiv 1 \pmod N, k \leq D$
    • Write $k=i\sqrt D + j, 0< i,j \leq \sqrt D$
    • $a^{\sqrt D}$
    $a^{2 \sqrt D}$
    ...
    $a^{D}$
    Find a match
    $a^{-1}$
    $a^{-2}$
    ...
    $a^{-\sqrt D}$
  • $\tilde{O}(\sqrt{D})$ run-time

Factoring Given the Residue Class of Divisors

  • After few iterations, our algorithm either finds $a$ of large order or deduces are all prime factors of $N$ are $1 \pmod D$
  • Lenstra (84), and Coppersmith, Howgrave-Graham and Nagaraj (08):
    • There is a deterministic polynomial time algorithm that given $N$ and $s\geq N^{1/4}$, finds all divisors of $N$ that equal $1 \pmod s$
  • If $D\geq N^{1/4}$ we can directly use their result
  • But we can even do better!
  • By combining (Lenstra, Coppersmith et al.)’s techniques with a recent algorithm of (Harvey–Hittmeir 22) we prove:
    • There is a deterministic algorithm that given $N$ and $D\geq N^{1/6}$, finds all divisors of $N$ that equal $1 \pmod D$ in time $D^{1/2}$

Coppersmith, Howgrave-Graham and Nagaraj

  • Suppose $p_0=sx_0+1$ is a divisor of $N$
  • $x_0$ is a root of $g(x)=sx+1$ modulo $p_0$
  • $x_0$ is a root of $g(x)^j N^{k-j}$ modulo $p_0^k$, as well as any integer linear combinations of these
  • Use LLL basis reduction to find a polynomial with small coefficients $h(x)$ in this lattice
  • Assuming $x_0$ is “small”, $h(x_0)$ will have to be zero over the integers as well
  • Find small roots of $h(x)$ over the integers

Covering the Entire Search Space

  • The last Lemma works for “small” $x_0$
  • To search the entire search space we split it to intervals and run the algorithm on each interval
    • Assume $p_0=sx_0+1\in[P-H,P+H]$ for some $P,H$
    • Define $g(x)=sx+1+P$ and $x'_0=x_0-P/s$
    • $g(x'_0)=p_0$ and $|x'_0|< H$ is a "small" root
    • When applying the lemma we want to maximize $H$ in order to minimize the number of intervals

Conclusion

  • Our Work
    • We provide a deterministic algorithm for finding elements of large multiplicative order, with improved parameter range
    • This contributes to improving the efficiency of part of the current fastest deterministic integer factorization algorithm
  • Open Problems
    • Deterministic factorization in $N^{1/6}$?
    • Deterministically finding a generator in the cyclic group $\mathbb{Z}_p^*$?
  • Thanks Ben Lee Volk
  • Questions?