质数的规律质数是什么意思数学

文章插图
对于其他大于1的自然数，都是合数，可以是1和自身以外的整数。显然，素数和素数相乘得到的数一定是合数。
长期以来，素数的研究被认为只有纯粹的数学意义，没有实用价值。直到 1970 年代，麻省理工学院 (MIT) 的三位数学家、和共同提出了一种公钥加密算法，该算法后来被广泛用于银行加密。RSA算法，人们意识到素数的巨大作用。
为什么在加密算法中使用素数？
这个问题涉及大数的素数分解。如果一个合数是由较小的两个素数相乘得到的，很容易分解成两个素数（除了1和它本身的组合），例如51的两个素数是3和17 。但是，如果两个大素数相乘得到一个非常大的合数，要逆分解成两个素数是非常困难的。比如分解成两个质因数后是557和919；（超过25亿），分解成两个素数后，就是29179和87013，这显然比之前的数字要难很多。
【质数的规律质数是什么意思数学】

文章插图

文章插图
截至今年 1 月，已知的最大素数是 2^-1，它有超过 2486 万位。即使对于超级计算机来说，也很难有效地分解两个素数相乘得到的合数，所以这个原理可以用在加密算法中。
什么是RSA加密算法？
RSA算法是一种非对称加密算法。用于加密和解密的密钥是不同的。用于解密的密钥对应于用于加密的密钥。假设A向B发送信息a，那么，a就是需要加密的信息；然后假设b是两个素数相乘得到的合数； c是一个与欧拉函数相关的数字，即公钥； d是c相对于欧拉函数值的模倒数，d是私钥。
信息加密
B生成合数b、公钥c、私钥d后，B将b和c传给A，d将保密，不传输。A使用公钥c对信息a进行加密，即计算a^c除以b的余数e，即a^c mod b=e，得到的e即为密文。因此，A 将密文 e 发送给 B 。
信息解密

文章插图
得到密文后，B使用私钥d解密密文e 。可以证明e^d除以b的余数正是信息a，即e^d mod b=a，从而完成信息的解密。

文章插图
由于合数b、公钥c和密文e都会被传输，这些信息可能会被窃取。如果窃取者想要破解信息，他需要知道私钥 d 。为了从公钥c计算出密钥d，需要对合数b进行素数分解。但是合数b是两个素数相乘得到的一个大数，要成功分解这个数是极其困难的。
目前RSA加密算法使用的大数有数百位，一般分解成两个数百位的素数。如果继续增加大数的位数，可以进一步降低被破解的风险。因此，RSA加密算法的安全性能是很有保障的，这也是它被广泛使用的原因。
郑重声明：本文版权归原作者所有，转载文章仅出于传播更多信息之目的。如果作者信息标注有误，请尽快联系我们修改或删除，谢谢。

质数的规律 质数是什么意思数学

质数的规律质数是什么意思数学