关于确定性地寻找模合数的高阶元素

《ACM Transactions on Algorithms》:On Deterministically Finding an Element of High Order Modulo a Composite

【字体: 大 中 小 】 时间:2026年10月24日 来源:ACM Transactions on Algorithms 1.4

编辑推荐:

   摘要我们提出了一个确定性算法,该算法在给定一个合数 $N$ 和目标阶 $D \geq N^{1/6}$ 的条件下,在时间 $D^{1/2 + 0(1)}$ 内运行,并找出一个乘法阶至少为 $D$ 的元素 $a \in \mathbb{Z}_N^*$,或者 $N$ 的一个非平凡

  

摘要

我们提出了一个确定性算法,该算法在给定一个合数 $N$ 和目标阶 $D \geq N^{1/6}$ 的条件下,在时间 $D^{1/2 + 0(1)}$ 内运行,并找出一个乘法阶至少为 $D$ 的元素 $a \in \mathbb{Z}_N^*$,或者 $N$ 的一个非平凡因子。我们的算法改进了 Hittmeir [14] 的算法,后者在更强的假设 $D \geq N^{2/5}$ 下设计了类似的算法。Hittmeir 的算法在 Hittmeir 和 Harvey [10, 12, 15] 最近取得的确定性整数分解算法突破中发挥了关键作用。当假设 $N$ 存在一个 $r \geq 2$ 次幂因子时,我们的算法在假设 $D \geq N^{1/(6r)}$ 的条件下提供相同的保证。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号