将 99 位长的大素数分解的问题

Question

号码是11288798737163099824081460333619591342348211143669600740142907237723834164788215269828199986523

def getfactors(number):
    factors = []
    for potentialFactor in range(1 , int(math.sqrt(number)) + 1):
        if number % potentialFactor == 0:
            factors.append(potentialFactor)
    return factors    

输入是

getfactors(112887987371630998240814603336195913423482111436696007401429072377238341647882152698281999652360869)

The program has been running for at least 3 hours and I still have no results from it yet. The code works with other numbers too. Is there any algorithm or method that I could use to speed this up?

Answer 1

由于 RSA 素数彼此接近，因此您的方法将花费大量时间来考虑给定数字。即使用埃拉托色尼筛法进行筛分也无济于事，因为您有一个 326 位的数字。能不能筛到163位，没办法。这比具有 300 位的第一个RSA 挑战 RSA-100稍大。

使用现有的库，如

• CADO-NFS ; http://cado-nfs.gforge.inria.fr/
• NFS 分解：http : //gilchrist.ca/jeff/factoring/nfs_beginners_guide.html
• 保理即服务https://seclab.upenn.edu/projects/faas/

实验

1. 我已经尝试过Pollard 的 p-1 算法，仍然运行了一天半，但还没有产生结果。这是预期的，因为B 边界必须2^55以成功概率存在1/27。CADO-NFS 成功后，我停止了实验。这是自实现的 Pollard 的p-1，可以在GMP-ECM 中找到优化的

2. 尝试了CADO-NFS。稳定版本可能不容易为新机器编译，所以更喜欢GitLab 中的活动版本。

   使用 4 个内核约 6 小时后，CADO-NFS 产生了结果。正如预期的那样，这是一个 RSA CTF/Challange。因为我不想破坏乐趣；这里是 SHA-512 的哈希承诺，它是用 OpenSSL 执行的；

   echo -n "prime x" | openssl sha512

27c64b5b944146aa1e40b35bd09307d04afa8d5fa2a93df9c5e13dc19ab032980ad6d564ab23bfe9484f64c4c43a993c09360f62f6d70a5759dfeabf59f18386

faebc6b3645d45f76c1944c6bd0c51f4e0d276ca750b6b5bc82c162e1e9364e01aab42a85245658d0053af526ba718ec006774b7084235d166e93015fac7733d

实验细节

• CPU : Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz

• RAM : 32GB - 不需要太多内存，至少在多项式选择和筛选期间。

• 专用核心：4

• 测试机 Ubuntu 20.04.1 LTS

• CUDA - 否

• gcc 版本 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)

• cmake 版本 3.16.3

• 外部库：Ubuntu 的规范中没有任何内容

• CODA-NFS 版本：在 23-01-2021 克隆的 GitLab 开发版本

• 位大小；

  • n 有 326 位（RSA-100挑战有 330位，1991 年被 Lenstra 破解）
  • p 有 165 位
  • q 有 162 位

在cado-nfs-2.3.0没有编制及提供有关HWLOC-错误 HWLOC_TOPOLOGY_FLAG_IO_DEVICES。请朋友测试编译，它对他们有用。这是一个较旧的 Linux 版本。所以我决定使用GitLab 版本。