素数
素数又称“质数”，指在大于1的自然数中只能被1和本身整除的整数。例如，2是一个素数，它只能被1和2整除；3也是；8不是素数，它还可以被2或4整除；13是素数，它只能被1和13整除；以此类推，5、7、11、13、17、23……是素数；4、6、8、10、12、14、16……不是素数。可以发现，2以上的素数必定是奇数，因为2以上所有的偶数都可以被2整除，所以不是素数。
素数的个数是无限的。顺便提一下，在大于1的整数中，不是素数的整数叫合数。1既不是素数也不是合数，整数0和所有负整数既不是素数也不是合数。
素数具有许多特殊性质，在数论中举足轻重。下面给出一个小素数序列：
2，3，5，6，11，13，17，19，23，29，31，37，41，43，47，53，59，...
亚里士多德和欧拉已经用反证法非常漂亮地证明了“素数有无穷多个”。
素性检测
常用的素数表通常只有几千个素数，显然无法满足密码学的要求，因为密码体制往往建立在极大的素数基础上，所以我们要为特定的密码体制临时计算符合要求的素数。这就牵涉到素性检测的问题。
判断一个整数是不是素数的过程叫素性检测。目前还没有一个简单有效的办法来确定一个大数是否是素数。理论上常用的方法有：
（1）wilson定理：若(n-1)!=-1(mod n)，则n为素数。
（2）穷举检测：若根号n不为整数，且n不能被任何小于根号n的正整数整除，则n为素数。
这些理论上的方法在n很大时计算量太大，不适合在密码学中使用。现在常用的素性检测的方法是数学家Solovay和Strassen提出的概率算法，即在某个区间上能经受住某个概率检测的整数就认为是素数。
因子分解问题是NP困难问题。如果n为200位十进制数，那么对n进行素数的因式完全分解大概要花费几十亿年。所以，密码体制大都是建立在大数的因式分解基础上的。
