《密码技术与物联网安全：mbedtls开发实战》 —3.2　素数

3.2　素数

定义3-1

设整数n≠0，±1，若除了因数±1和±n之外，n没有其他的因数，那么称n为素数（或质数或不可约数），否则n为合数。

例如，整数2、3、7都是素数，而4、6、10、15、32都是合数。素数，又称质数或不可约数。素数的概念虽然简单，但是人类从未停止过有关素数的研究。若一个整数小于100，通过简单的运算就可判断该整数是否为素数，例如24=2×2×2×3，所以24为一个合数；而59=1×59，所以59为一个素数。

素数还有一个显著特点：若给定两个素数p和q，计算乘积n=p·q 较为容易；但给定一个整数n，求解其两个素因数却非常困难。这便是公钥加密RSA算法的基础。例如：

p=20000000000000002559，q=80000000000000001239

n=p·q=1600000000000000229500000000000003170601

表3-2罗列了前100个素数。

表3-2　前100个素数

判断素数的方法包括平凡除法（厄拉托赛师筛选法）、费马检验、Miller-Rabin检验等。这些素数检测方法可参考《信息安全数学基础（第2版）》一书。