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