頭條新聞

RSA-576 已分解

作者：Eric W. Weisstein

2003 年 12 月 5 日——12 月 3 日，在大網際網路梅森素數搜尋於 12 月 2 日宣佈發現已知最大素數（ 頭條新聞，2003 年 12 月 2 日）後的第二天，德國聯邦資訊科技安全域性 (BSI) 的一個團隊宣佈分解了 174 位數字

1881 9881292060 7963838697 2394616504 3980716356 3379417382 7007633564 2298885971 5234665485 3190606065 0474304531 7388011303 3967161996 9232120573 4031879550 6569962213 0516875930 7650257059

稱為 RSA-576。

RSA 數字是具有正好兩個 素因子（即所謂的 半素數）的 合數，這些數字已在 RSA Security^® 的因數分解挑戰賽中列出。

雖然合數被定義為可以寫成較小數字（稱為 因子）乘積的數字（例如，6 = 2 x 3 是合數，因子為 2 和 3），但 素數 沒有這種分解（例如，7 除了 1 和自身之外沒有任何因子）。因此，素因子代表給定正整數的基本（且唯一的）分解。RSA 數字是特殊型別的合數，特意選擇難以分解，並且透過它們包含的位數來識別。

雖然 RSA-576 比本週早些時候宣佈的 6,320,430 位怪獸 梅森素數 小得多，但它的分解意義重大，因為數字具有一個奇特的屬性，即證明或反駁一個數字是素數（“素性測試”）似乎比實際識別一個數字的因子（“素因數分解”）容易得多。因此，雖然將兩個大數 p 和 q 相乘在一起是微不足道的，但如果僅給出它們的乘積 pq，則確定因子可能極其困難。透過一些巧妙的方法，此屬性可用於建立實用且高效的電子資料加密系統。

RSA 實驗室贊助 RSA 因數分解挑戰賽，以鼓勵對計算數論和分解大整數的實際難度進行研究，並且因為它有助於 RSA 加密 公鑰密碼演算法的使用者選擇適合的安全級別的金鑰長度。現金獎勵將頒發給第一個分解每個挑戰數字的人。

RSA 數字最初以 10 個 十進位制 數字的間隔分佈在一到五百位數字之間，獎金根據複雜的公式頒發。這些原始數字根據十進位制數字的數量命名，因此 RSA-100 是一個百位數字。隨著計算機和演算法變得更快，未分解的挑戰數字從獎金列表中刪除，並替換為一組具有固定現金獎勵的數字。此時，命名約定也發生了變化，因此尾隨數字表示數字的 二進位制 表示中的位數。因此，RSA-576 有 576 個二進位制數字，轉換為十進位制為 174 位數字。

當 R. Rivest、A. Shamir 和 L. Adleman 使用 129 位數字（稱為 RSA-129）釋出最早的公鑰訊息之一，併為該訊息的解密提供了 100 美元的獎勵時，RSA 數字受到了廣泛關注 (Gardner 1977)。儘管當時普遍認為破解 RSA-129 編碼的訊息需要數百萬年，但它在 1994 年被分解，使用分散式計算，利用遍佈全球的網路計算機執行多項式 二次篩法 (Leutwyler 1994)。所有集中式數字運算的結果是對編碼訊息的解密，產生了深刻的明文訊息“The magic words are squeamish ossifrage.”（ossifrage 是一種罕見的食腐猛禽，在歐洲的山區發現。）

在 RSA-129 分解之後，又分解了 RSA-100、RSA-110 和 RSA-120。挑戰數字 RSA-130、RSA-140、RSA-155 和 RSA-160 也在 1996 年至今年 4 月之間相繼分解。（有趣的是，RSA-150 在從 RSA 挑戰列表撤回後顯然仍然未分解。[但是，請參閱附言。]）

12 月 2 日，Jens Franke 釋出了一封電子郵件，宣佈分解了最小的獎金數字 RSA-576。該分解是使用一種稱為通用數域篩法的 素因數分解演算法 完成的。使用此篩法找到的兩個 87 位因子是

3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317 x 4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305 2071125636 3590397527

並且可以輕鬆地將它們相乘來驗證它們是否確實給出了原始數字。

Franke 的註釋詳細介紹了分解過程，其中“格子”篩選由 J. Franke 和 T. Kleinjung 在波恩大學科學計算研究所和純數學研究所、波恩馬克斯·普朗克數學研究所和埃森實驗數學研究所使用硬體完成；“線”篩選由 CWI 的 P. Montgomery 和 H. te Riele、F. Bahr 及其家人以及 NFSNET（當時由 D. Leclair、P. Leyland 和 R. Wackerbarth 組成）完成。然後，在 BSI 的支援下完成了此資料的後處理，以構建實際因子。

由於他們的努力，該團隊將獲得 RSA Security 提供的 10,000 美元現金獎勵。但是，尋求獎勵的人不必氣餒。如下表所示，RSA-640 至 RSA-2048 仍然開放，為那些足夠聰明和堅持不懈地追蹤它們的人提供 20,000 美元至 200,000 美元的獎勵。開放挑戰數字的列表可以從 RSA 下載，也可以從 包存檔中以 Mathematica 包的形式下載。

附言 2004 年 8 月 24 日新增：RSA-150 已被 Aoki 等人分解為兩個 75 位素數，見日期為 2004 年 4 月 16 日的 預印本。