RSA 數

RSA 數是難以分解的合數，正好有兩個素因子（即所謂的半素數），這些數曾列於 RSA Security® 的分解挑戰中——該挑戰現已撤銷且不再有效。

儘管 RSA 數遠小於已知的最大素數，但它們的因式分解意義重大，因為數字有一個奇特的性質，即證明或反證一個數是素數（“素性測試”）似乎比實際識別一個數的因子（“素因數分解”）容易得多。因此，雖然將兩個大數 和 相乘是微不足道的，但如果只給出它們的乘積 ，則確定因子可能極其困難。透過一些巧妙的設計，這種性質可以用來建立實用且高效的電子資料加密系統。

RSA 實驗室發起 RSA 分解挑戰賽，旨在鼓勵對計算數論和分解大整數的實際難度進行研究，並且因為它有助於 RSA 加密 公鑰密碼演算法的使用者選擇合適的金鑰長度以達到適當的安全級別。

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

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

(Leutwyler 1994, Cipra 1996)。

在電視犯罪劇集《數字追兇 (NUMB3RS)》第一季的“頭號嫌疑犯”一集中提到了 RSA-129。

1999 年 2 月 2 日，由 H. te Riele 領導的小組完成了 RSA-140 的因式分解，分解為兩個 70 位素數。在 2004 年 4 月 16 日的預印本中，Aoki et al. 將 RSA-150 分解為兩個 75 位素數。1999 年 8 月 22 日，由 H. te Riele 領導的小組完成了 RSA-155 的因式分解，分解為兩個 78 位素數 (te Riele 1999b, Peterson 1999)。12 月 2 日，Jens Franke 散發了一封電子郵件，宣佈分解了最小的獎金數 RSA-576 (Weisstein 2003)。這種分解為兩個 87 位因子的方法是使用一種稱為通用數域篩法 (GNFS) 的素因數分解演算法完成的。2005 年 5 月 9 日，Franke 領導的小組宣佈將 RSA-200 分解為兩個 100 位素數 (Weisstein 2005a)，2005 年 11 月，同一小組宣佈分解了 RSA-674 (Weisstein 2005b)。

2010 年 1 月 7 日，Kleinjung 宣佈透過數域篩法分解了 768 位、232 位數字的 RSA-768，這創下了分解通用整數的記錄。兩個因子都具有 384 位和 116 位數字。總篩選時間約為 1500 AMD64 年 (Kleinjung 2010, Kleinjung et al. 2010)。

如下表所示，雖然挑戰賽已撤銷，但大多數 RSA-704 到 RSA-2048 的數字從未被分解。

數字	十進位制位數	獎金	已分解 (參考文獻)
RSA-100	100		四月 1991
RSA-110	110		四月 1992
RSA-120	120		六月 1993
RSA-129	129		四月 1994 (Leutwyler 1994, Cipra 1995)
RSA-130	130		四月 10, 1996
RSA-140	140		二月 2, 1999 (te Riele 1999a)
RSA-150	150		四月 6, 2004 (Aoki 2004)
RSA-155	155		八月 22, 1999 (te Riele 1999b, Peterson 1999)
RSA-160	160		四月 1, 2003 (Bahr et al. 2003)
RSA-200	200		五月 9, 2005 (see Weisstein 2005a)
RSA-576	174		十二月 3, 2003 (Franke 2003; see Weisstein 2003)
RSA-640	193		十一月 4, 2005 (see Weisstein 2005b)
RSA-704	212	withdrawn	七月 1, 2012 (Bai et al. 2012, Bai 2012)
RSA-768	232	withdrawn	十二月 12, 2009 (Kleinjung 2010, Kleinjung et al. 2010)
RSA-896	270	withdrawn
RSA-1024	309	withdrawn
RSA-1536	463	withdrawn
RSA-2048	617	withdrawn