素數分解（102 位）

我有一個由 102 位數字組成的數字，我需要考慮它。我在 alpertrom.com.ar 上執行了它，但如果我數好的話，最多需要 40 個小時。有什麼方法可以手工製作（愚蠢的問題），我的意思是簡化程序的計算？或者，也許任何人都可以將其分解。教授可能只是在測試我們處理器的可計算性。

這是號碼：166045890368446099470756111654736772731460671003059151938763854196360081247044441029824134260263654537

您的 102 位數字比具有 330 位的第一個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/

Factoring as a Service 項目旨在允許任何人使用 Amazon EC2 平台在短短 4 小時內以不到 100 美元的價格進行 512 位整數的因式分解，只需最少的設置。

---

本實驗

99位數字的因數 $ n = $ 112887987371630998240814603336195913423482111436696007401429072377238341647882152698281999652360869.

1. 我試過波拉德的 $ p $ -1 算法，仍然執行了一天半，還沒有產生結果。這是預期的，因為B 界限必須在附近 $ 2^{55} $ 有成功機率 $ \dfrac{1}{27} $ . CADO-NFS 成功後我停止了實驗。這是自行實現的 Pollard 的 $ p $ -1，可以在GMP-ECM中找到一個優化的
2. 嘗試了 CADO-NFS。穩定版本可能不容易為新機器編譯，所以更喜歡GitLab中的活動版本。

使用 4 個核心約 6 小時後，CADO-NFS 產生了結果。這是一個 RSA CTF/挑戰，我不想破壞樂趣；這裡是 SHA-512 的雜湊承諾，它是用 OpenSSL 執行的；

echo -n "prime x" | openssl sha512

27c64b5b944146aa1e40b35bd09307d04afa8d5fa2a93df9c5e13dc19ab032980ad6d564ab23bfe9484f64c4c43a993c09360f62f6d70a5759dfeabf59f18386

faebc6b3645d45f76c1944c6bd0c51f4e0d276ca750b6b5bc82c162e1e9364e01aab42a85245658d0053af526ba718ec006774b7084235d166e93015fac7733d

---

使用 CADO-NFS 進行 6 核 RSA 挑戰的實驗

核心數量對於減少時間非常重要，因為在 EC2 平台中可以將 512 位破解為 4 小時。

---

實驗細節

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

• 記憶體：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 版本：GitLab 開發版本複製於 23-01-2021

• 位大小；

  • $ n $ 有 326 位
  • $ p $ 有 165 位
  • $ q $ 有 162 位

cado-nfs-2.3.0沒有編譯並給出關於 HWLOC- 的錯誤HWLOC_TOPOLOGY_FLAG_IO_DEVICES。請朋友測試編譯，它對他們有用。這是一個較舊的 Linux 版本。所以我決定使用GitLab 版本。

---

• **注意：**這個問題沒有考慮到 OP 的原始數字。
• 歷史記錄： RSA-100挑戰有 330 位，並在 1991 年被 Lenstra 打破。

引用自：https://crypto.stackexchange.com/questions/89560