2.6 素数有用吗

几个素数相乘非常简单，反过来，将一个数分解成素数相乘的形式就很难了！在数学中，把一个合数变成素数乘积的过程被称为质因子分解。对于一台计算机来说，把两个很大的素数相乘，即使每个素数长达100位，计算出结果也并不难。然而，把一个很大的数分解成素数的乘积就困难了，即使对于超级计算机来说也是如此。这个难点被李维斯特、萨莫尔和阿德曼三位数学家在1977年发明RSA加密算法时利用。三位年轻的数学家和计算机科学家发明了RSA密码系统，编制了由两个素数相乘得到的一个129位数字构成的密码数（合数），结果经过五大洲的600多位数学家用1600台计算机联网，合作攻关8个月才破译了该密码，即把这个密码合数分解为两个素数的乘积，就目前的计算机能力，分解一个100位整数需要几分钟时间，但是要分解一个200位的整数则至少需要上千年！这使得素数在设定密码方面相当适合。当你在互联网上消费的时候，交易的细节都是通过这种方式隐藏起来的，代码的“锁”是非常大的数字，而“钥匙”则是由它的素数组成的，现在人们已经将大素数用于现代密码设计领域。

RSA密码系统的三位创始人

这其中的根本原因在于：将几个素数相乘相对容易得多，但将一个很大的数分解成若干素数的乘积则是一个极其困难的问题。在这种密码的设计中，需要使用较大的素数，素数越大，密码被破译的可能性就越小。这个问题也是目前数学与计算机领域的核心问题之一，至今没有有效的方法解决，因此可以确保RSA算法的安全性。