素数的应用领域

或称质数，是指只能被1和它本身整除的大于1的自然数。对于其他大于1的自然数，都是合数，可以被除了1和它本身以外的其他数整。很明显，质数乘以质数得到的数一定是合数。

长期以来，素数的研究被认为只有纯数学意义，而没有实际价值。直到20世纪70年代，美国麻省理工学院(MIT)的三位数学家Lee West、Samol和Aderman共同提出了一种公钥加密算法，即后来广泛应用于银行加密的RSA算法，人们才意识到素数的巨大作用。

为什么素数可以用在加密算法中？

这涉及到大数的质因数分解。如果一个合数是由两个较小的素数相乘得到的，就很容易分解成两个素数(1和它本身的组合除外)。例如，51的两个质因数是3和17。但是，如果两个非常大的质数相乘得到一个非常大的合数，那么要把这个数反过来分解成两个质数是非常困难的。比如511883，分解成两个质因数后就是557和919；238952327(超过25亿)，分解成两个质因数后就是29179和87013。这个难度显然比上一个大很多。

截至今年1月，已知最大的素数是2 825899331，有2486多万位数。即使在超级计算机中，也很难对两个素数相乘得到的合数进行有效的因式分解，因此可以在加密算法中使用这一原理。

什么是RSA加密算法？

RSA算法是一种非对称加密算法。用于加密和解密的密钥是不同的，用于解密的密钥对应于用于加密的密钥。假设A发送信息A给B，那么A就是需要加密的信息；假设b是两个素数相乘得到的合数；c是与欧拉函数相关的数，是公钥；D是C关于欧拉函数值的逆模，D是私钥。

信息加密

B生成合数B后，公钥C和私钥D，B将B和C传递给A，D保密，不传输。用公钥C of A加密信息A，即计算A C除以B的余数E，即A C mod B = E，得到的E就是密文。所以，A把密文E发给b。

信息解密

B得到密文后，用私钥d解密密文E，可以证明ed除以B的余数就是信息a，即e d mod b = a，从而完成信息的解密。

由于合数B、公钥C和密文E都将被传输，这些信息可能被窃取。如果小偷想破解信息，需要知道私钥D，如果想通过公钥C计算出密钥D，就需要用质因数对合数B进行因式分解。但合数B是两个素数相乘得到的大数，要成功分解这个数是极其困难的。

目前RSA加密算法使用的大数有几百个，一般分解成两个几百比特的素数。如果继续增加大数的位数，可以进一步降低被破解的风险。所以RSA加密算法的安全性能是非常安全的，这也是它会被广泛使用的原因。