下载掌阅APP，畅读海量书库
立即打开
阿拉伯古代民间故事集《天方夜谭》又名《一千零一夜》，这“1001”是一个很有趣的数。
如果有人问：“1001是质数，还是合数？”你大概不会马上作出正确的回答，因为因数分解并不容易，更何况1001中没有常见因数2，3和5。
如果你抱着侥幸心理回答说，1001是质数，那么你就错了。因为1001虽不是2，3，5的倍数，但它恰恰是7，11，13的倍数，而且
1001=7×11×13。
利用1001的分解式，有人设计了一则魔术：
“请你心中想一个三位数。”魔术师说。
“想好了。”小明心中想的数是123。
“请你把它连写两遍，变成一个六位数。”魔术师又发出指令。
小明很听话，在心中默默地记着六位数123 123。
“将它除以7。”
小明打开手机上的计算器，得到17 589。
“再除以11。”
得到1599。
“再除以13，结果是多少？和你心中想的数有什么关系？”
“咦，结果就是我想的数123！”
这个魔术安排得十分巧妙，我们来分析一下它的奥秘所在。
首先是因为123这个数连写两遍，就是乘以1001。
123 123=123×1001，
其次又因为刚刚说过的1001=7×11×13，于是，
于是得到123。
1001这样的数分解已经有点儿难度了。把一个大数因数分解更是一件很困难的事情，所以，特工人员设计了一种高级的密码系统，要破译这种密码，必须掌握把一个大数分解成质因数的积的本领。这种密码系统叫RSA，是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。RSA就是用3位发明者姓名的首字母组成的。
这种密码看来是万无一失了，因为那时人们对分解一个50位的数还束手无策。
1984年2月13日，美国《时代》周刊报道了惊人的消息：在一个星期之前，数学家们在32小时内分解了一个69位的大数，创造了世界纪录。
这件大工程开始于一个偶然的机会。1982年秋天，桑迪亚国家实验室应用数学部主任辛摩斯与克雷计算机公司的一位工程师凑巧在一起，他们一边喝啤酒，一边聊天。辛摩斯抱怨说，因数分解工作全靠尝试，实在难以完成。那位工程师马上说克雷计算机能同时抽样整串的数字，或许特别适合因数分解。于是，他们合作起来，编制了专门程序，在克雷计算机上接二连三成功地分解了58位、60位、63位和67位数。最后他们分解了一个69位数，从而解决了一个遗留了300年之久的难题。
1978年，RSA的发明人在《科学美国人》上公布了一个密文，涉及一个128位数，挑战说：悬赏100万美元，征求解密者，也就是谁能够将这个大数分解成质因数，谁就可以获得这100万美元的奖金。直到1995年4月26日，路透社才报道说，600多位计算机专家动用了1600多台计算机，持续工作8个月，才把这个128位数分解为两个质数。可见大数的质因数分解之难。
不久前，美国科学家宣布，240位的十进制整数分解成功（相当于795位的二进制数），找到了它的两个大质数因子。这是至今已经公布的最高纪录，此前的纪录是768位二进制整数。
整数分解是加密学的基石，一旦实现快速的整数分解，现代的公钥加密就会失效。目前主流的加密强度是2048位二进制数的密钥，所以RSA还是安全的。
不久的将来，科学家们一定会分解出更大的大数，到那时，RSA密码系统就岌岌可危了！