素数理论在密码学的应用

   密码学涉及到将需要保密的信息打乱，使得只有接受者才能整理出它们，而别的任何可能截获它们的人都无法整理出它们。这种打乱的过程需要使用保密的密码本，而整理这些信息按管理只需要接收者反过来使用密码本就行了。在这个程序中，密码本是保密环节中最薄弱的一环。首先，接收者和发送者必须约定密码本的详细内容，而这种信息的交流是一个有泄密风险的过程。如果敌方能截获正在交流的密码本，那么他们就能译出此后所有的信息。其次，为了保持安全性，密码本必须定期更改，而每一次更改时，都有新的密码本被截获的危险。
   密码本的问题围绕着下面的事实展开：它的使用，一次是打乱信息，另一次是反过来整理出信息，而整理信息几乎与打乱信息同样容易。然而，经验告诉我们，在许多情况中整理要比打乱困难的多——打碎一个鸡蛋是相对容易的，而重新拼好它则困难的多。
   在20世纪70年代，会特菲尔德·迪菲和马丁·海尔曼提出了这样的思想：寻找一种按一个方向很容易进行，而按相反方向进行则不可思议的困难的数学程序。这种程序将会提供十分完美的密码本。举例来说，我可以有自己用的、由两部分组成的密码本，并且在公用指南中公开它的用于打乱信息的那部分。于是，任何人都可以向我发送打乱过的信息，但是只有我知道密码本中用于整理信息的那一半。虽然人人都了解密码本中关于打乱信息的那部分，但是它和密码本中用来整理信息的那部分毫无联系。
   在1977年，麻省理工学院一群数学家和计算机专家罗纳德·里维斯特、爱迪·沙弥和伦纳德·阿德李曼认识到素数可能是易打乱/难整理过程的理想的基础。为了制成我自己的私人密码本，我会取两个大素数，每一个多达80个数字，然后将它们乘起来得到一个大得多的非素数。为了打乱信息所需要的一切，就是知道这个大的非素数，它们称为素因数。现在我可以公开大的非素数，也即密码本中打乱信息的那一半，而自己保存那两个素因数，也即密码本中整理信息的那一半。重要的是，即使人人都知道这个大的非素数，他们要判断出那两个素因数却非常困难。
   举一个简单的例子，我可以交出非素数589，这可能会使每个人都能代我打乱信息。然而，我将保守589的两个素因数的秘密，结果只有我能够整理信息。如果别的人能判断出这两个素因数，那么他们也能整理我的信息，但是即使是对这个不大的数，两个素因数是什么也不是显而易见的。在589这个情形中，在台式电脑上只要花几分钟就可以算出两个素因数实际上是31和19，所以我的密码本的秘密不会持久。
然而，实际上我公布的非素数将会有100位以上的数字，这就使找出他的素因数的任务变得几乎是不可能的。即使用世界上最快的计算机来将这个巨大的非素数（打乱信息的密码）分解成它的两个素因数（整理信息的密码），也要花几年时间才能得到答案。于是，为挫败外国间谍，我仅仅需要每年一次更改我的密码本。每年一次我宣布我的巨大的非素数，任何人都想尝试整理我的信息，就必须从头开始设法算出这两个素因数。