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

基本信息

  • 论文ID: 2506.07668
  • 标题: On Deterministically Finding an Element of High Order Modulo a Composite
  • 作者: Ziv Oznovich, Ben Lee Volk (Efi Arazi School of Computer Science, Reichman University, Israel)
  • 分类: cs.DS (Data Structures and Algorithms), math.NT (Number Theory)
  • 提交时间: 2025年6月11日 (arXiv v3)
  • 论文链接: https://arxiv.org/abs/2506.07668

摘要

本文提出了一个确定性算法，给定合数 NN 和目标阶 D≥N1/6D \geq N^{1/6}，算法在 D1/2+o(1)D^{1/2+o(1)} 时间内运行，要么找到一个乘法阶至少为 DD 的元素 a∈ZN∗a \in \mathbb{Z}_N^*，要么找到 NN 的一个非平凡因子。该算法改进了 Hittmeir 的算法，后者需要更强的假设 D≥N2/5D \geq N^{2/5}。当 NN 具有 rr 次幂因子（r≥2r \geq 2）时，算法在假设 D≥N1/6rD \geq N^{1/6r} 下提供相同的保证。

研究背景与动机

问题背景

  1. 整数分解的挑战: 整数分解是计算数论中的核心问题。目前最好的随机算法（如数域筛法）具有次指数复杂度，而最好的确定性算法直到最近还是强指数的。
  2. 确定性算法的重要性: 虽然理论上认为每个随机算法都可以被确定性算法以多项式慢化模拟，但获得无条件的去随机化结果在复杂性理论和算法设计中仍具有重要意义。
  3. 高阶元素的作用: Hittmeir 和 Harvey 的突破性工作表明，确定性地找到具有大乘法阶的元素是设计高效确定性分解算法的关键。

研究动机

  1. 改进参数范围: Hittmeir 的算法要求 D≥N2/5D \geq N^{2/5}，这个条件相对严格，限制了算法的应用范围。
  2. 提升分解算法: 在 Harvey-Hittmeir 分解算法中，找高阶元素的步骤运行时间为 N1/5+o(1)N^{1/5+o(1)}，成为算法的瓶颈之一。
  3. 理论意义: 去随机化是理论计算机科学的重要问题，在数论算法中实现去随机化具有深远的理论意义。

核心贡献

  1. 参数改进: 将目标阶的要求从 D≥N2/5D \geq N^{2/5} 降低到 D≥N1/6D \geq N^{1/6}，显著扩展了算法的适用范围。
  2. 运行时间保持: 在放宽参数要求的同时，保持了 D1/2+o(1)D^{1/2+o(1)} 的运行时间复杂度。
  3. rr 次幂情况的优化: 当 NN 具有 rr 次幂因子时，进一步将要求降低到 D≥N1/6rD \geq N^{1/6r}。
  4. 分解算法改进: 提供了新的分解子程序，改进了已知残基类信息下的因子分解方法。
  5. 理论工具: 证明了连续整数中满足特定同余条件的元素数量的更紧界限。

方法详解

任务定义

输入: 合数 NN 和目标阶 D≥N1/6D \geq N^{1/6}输出: 要么是 ZN∗\mathbb{Z}_N^* 中乘法阶至少为 DD 的元素 aa，要么是 NN 的非平凡因子 时间复杂度: D1/2+o(1)D^{1/2+o(1)}

算法架构

主算法结构 (Algorithm 4.1)

算法采用迭代搜索策略，主要包含以下步骤：

  1. 预处理: 使用 Strassen 方法检查小因子
  2. 迭代搜索: 对 a=2,3,4,…a = 2, 3, 4, \ldots 进行搜索
  3. 阶计算: 使用改进的 Baby-step Giant-step 方法
  4. 信息积累: 维护变量 MM 记录已检查元素阶的最小公倍数
  5. 最终分解: 当 MM 足够大时使用新的分解算法

核心技术改进

1. 连续根的界限改进 (Claim 2.6)

对于大整数 N, ℓ，如果 N 有素因子 p > 2ℓ，
则在 m = 10√ℓ 个连续整数 {a, a+1, ..., a+m} 中，
必存在元素 b 使得 b^ℓ ≢ 1 (mod N)

这将 Hittmeir 算法中 O(M)O(M) 的搜索复杂度改进为 O(M)O(\sqrt{M})。

2. 残基类分解算法 (Theorem 3.2) 给定 NN 和 s≥Nαs \geq N^α（α≤1/(4r)α \leq 1/(4r)，gcd⁡(N,s)=1\gcd(N,s) = 1）， 算法能在 N1/(4r)−α+o(1)N^{1/(4r)-α+o(1)} 时间内找到所有满足 p≡1(mods)p \equiv 1 \pmod{s} 的 rr 次幂因子。

技术创新点

1. 多项式构造的改进

在 Harvey-Hittmeir 算法基础上，将基础多项式从 f(x)=x+Pf(x) = x + P 改进为： g(x)=x+s′+s′(P−P~)g(x) = x + s' + s'(P - \tilde{P}) 其中 s′s' 是 ss 模 NN 的逆，P~\tilde{P} 是 PP 模 ss 的余数。

2. 搜索空间的缩减

利用素因子 p≡1(mods)p \equiv 1 \pmod{s} 的信息，将搜索根的大小从 HH 缩减到约 H/sH/s，从而将搜索区间数量减少 ss 倍。

3. LLL 格基约化的应用

构造多项式系统：

N^{m-\lfloor i/r \rfloor} g(x)^i, & 0 \leq i < rm \\ g(x)^i, & rm \leq i < d \end{cases}$$ 通过 LLL 算法找到短向量，对应于系数较小且在目标根处为零的多项式。 ## 实验设置 ### 理论分析框架 本文主要进行理论分析，通过数学证明验证算法的正确性和复杂度： 1. **正确性证明**: 证明算法在每个终止点都输出正确结果 2. **复杂度分析**: 详细分析每个步骤的时间复杂度 3. **参数优化**: 通过理论分析确定最优参数设置 ### 关键引理验证 - **Lemma 2.5** (Forbes等): 多项式系统根的数量界限 - **Claim 2.6**: 连续整数中不满足同余条件的元素存在性 - **Claim 3.3**: 残基类约束下根大小的界限 ## 实验结果 ### 理论结果 1. **主定理 (Theorem 1.1)**: - 参数要求: $D \geq N^{1/6}$（vs. Hittmeir的 $N^{2/5}$） - 运行时间: $D^{1/2+o(1)}$（保持不变） 2. **$r$ 次幂情况 (Theorem 4.2)**: - 参数要求: $D \geq N^{1/6r}$ - 运行时间: $D^{1/2+o(1)}$ 3. **分解算法 (Theorem 3.2)**: - 条件: $s \geq N^α$，$α \leq 1/(4r)$ - 运行时间: $N^{1/(4r)-α+o(1)}$ ### 复杂度改进 - **搜索步数**: 从 $O(M)$ 改进到 $O(\sqrt{M})$ - **参数范围**: 指数从 $2/5$ 降低到 $1/6$ - **分解效率**: 在已知残基信息时显著提升 ### 与相关工作对比 | 算法 | 参数要求 | 运行时间 | 年份 | |------|----------|----------|------| | Hittmeir | $D \geq N^{2/5}$ | $D^{1/2+o(1)}$ | 2018 | | GFHP | $D \geq N^{1/4r}$ | $D^{1/2+o(1)}$ | 2025 | | 本文 | $D \geq N^{1/6}$ | $D^{1/2+o(1)}$ | 2025 | ## 相关工作 ### 确定性分解算法发展 1. **经典方法**: Pollard-Strassen 算法 ($N^{1/4+o(1)}$) 2. **近期突破**: Hittmeir-Harvey 算法 ($N^{1/5+o(1)}$) 3. **随机算法**: 数域筛法等亚指数算法 ### 高阶元素查找 1. **随机方法**: 随机元素通常具有大阶 2. **确定性挑战**: 如何确定性地找到此类元素 3. **应用**: 在分解算法中的关键作用 ### 格基约化应用 1. **Coppersmith 方法**: 寻找多项式小根 2. **Harvey-Hittmeir**: $r$ 次幂因子分解 3. **本文扩展**: 结合残基类信息的改进 ## 结论与讨论 ### 主要结论 1. 成功将高阶元素查找的参数要求从 $N^{2/5}$ 降低到 $N^{1/6}$ 2. 保持了 $D^{1/2+o(1)}$ 的最优运行时间 3. 为确定性分解算法提供了更好的子程序 ### 局限性 1. **素数情况**: 算法对素数输入可能无法产生有用输出 2. **参数限制**: 仍需要 $D \geq N^{1/6}$ 的下界 3. **实际效率**: 理论改进在实际应用中的效果需要验证 ### 未来方向 1. **突破 1/5 屏障**: 在分解算法中应用本算法可能带来进一步改进 2. **素域生成元**: 确定性找到 $\mathbb{Z}_p^*$ 的生成元 3. **离散对数**: 改进确定性离散对数算法 ## 深度评价 ### 优点 1. **理论创新**: 巧妙结合了多个数学工具，实现了参数的显著改进 2. **技术深度**: 对 Harvey-Hittmeir 算法的扩展展现了深厚的技术功底 3. **实用价值**: 为确定性分解算法提供了更好的构建模块 4. **证明严谨**: 数学推理严密，复杂度分析详细 ### 不足 1. **实验验证**: 缺乏实际实现和性能测试 2. **常数因子**: $o(1)$ 项可能在实际中不可忽略 3. **适用范围**: 对某些特殊情况（如素数）处理有限 ### 影响力 1. **理论贡献**: 推进了确定性数论算法的发展 2. **方法价值**: 提供的技术可能适用于其他相关问题 3. **后续研究**: 为进一步改进分解算法奠定基础 ### 适用场景 1. **理论研究**: 复杂性理论和算法设计 2. **密码学**: 需要确定性保证的安全应用 3. **数论计算**: 大整数相关的数学计算 ## 参考文献 - [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 --- 本论文在确定性数论算法领域做出了重要贡献，通过巧妙的技术创新实现了参数的显著改进，为未来的研究提供了有价值的工具和思路。