2.4 有关素数的运算
众所周知，一个素数是一个大于1的自然数（一个比0大的整数），它的因数只有1和它本身。一个合数是一个大于1并且非素数的自然数。
素数在某些应用中起到重要的作用，在这些应用中素数的特质使得它们能够使特定程序变得简单或繁琐。例如，某些加密程序使用两个大素数的积来保证安全性。将一个由两个大素数相乘得到的数分解成两个大素数是十分困难的，而正是这个事实保证了算法的安全性。
以下章节将讨论一些处理素数的常见算法。
2.4.1 寻找素数因子
寻找一个数的素因子最显而易见方法是尝试将这个数用比其小而大于等于2的整数试除。当一个可能的因子将这个数整除时，保存这个因子，用该因子除这个数，然后继续尝试更多的因子。注意，每次试除需要将同一个因子再重复除一次，以防这个数含有多于一个该因子。
例如，为了找到127的素因子，需要将127被2、3、4、5…除，直到126。
下列伪代码展示了这个算法：
如果这个数是N，那么这个算法的运行时是O(N)。
通过三个重要注意事项可以来极大地改进这个方法：
不需要检验这个数是否能够被任何一个除了2以外的偶数整除，因为如果它能够被任意偶数整除，则其一定能够被2整除。这意味着只需要检验2和奇数是否能整除该数，而不用检查所有可能因数。这样做能够将运行时间减半。
仅需要检查不大于待检测数字平方根的因子。如果n＝p×q，p或q一定要小于等于sqrt(n)。（如果这两个数都比sqrt(n)大，它们的积一定比n大。）如果检查了比sqrt(n)小的可能因子，若发现其中较小因子，而用这个较小因子整除n时，则会发现另一个因子。这把运行时间降到了O(sqrt(n))。
每次用一个因子试除这个数时，可以更新需要检查的可能因子的上界。
这些注意事项产生了以下改进的算法：
注 这个素因数分解算法的运行时间复杂性为O(sqrt(N))，N是该算法正在进行素因数分解的数，因此当这个数比较小时，这个算法运行速度相当快。如果N变得相当大，甚至O(sqrt(N))也不够快。例如，如果N为100位，那么sqrt(N)就有50位。如果这个数恰好是一个素数，那么即使运行速度很快的计算机也不能在合理时间内尝试所有的可能因子。这就是加密算法保密性得以保证的原因。
2.4.2 寻找素数
假设程序需要提取一个大素数。（这是另一个加密算法所需要的程序。）一种找到这些素数的方法是使用之前章节介绍的算法来检验大量的数，以寻找其中的素数。这种方法只适用于较小的数，但是对于较大的数，这种算法过于缓慢。
埃拉托色尼筛法（the sieve of Eratosthenes）是一种找出给定范围内所有素数的简单方法。此方法适用于较小的数，因为它需要一个由所有考虑到的数构成的表。因此，当数过大时，这种方法会占用十分大的内存空间。
其基本思想是建立一个以2和上界之间所有数构成的表。删去所有2的倍数（不包括2本身）。然后，从2开始，检索该表来寻找下一个没有被删去的数（例如3）。删去所有这个数的倍数（不包括这个数本身）。注意，其中有些数也是2的倍数，它们已经被删去了。重复这一步，寻找下一个没有被删去的数，删去其所有倍数，直到计算到上界的平方根。这时所有没有被删去的数就都是素数了。
以下伪代码展示了该基本算法：
可以看到该算法的运行时间复杂度为O(N×log(log N))，这超出了这本书的讨论范围。
2.4.3素性测试
之前2.4.1节中介绍的算法将数分解成因子。一种确定某数是否为素数的方法是使用这个算法来尝试分解它。如果这个算法一个因子都找不到，那么该数为素数。
2.4.1节中谈到这个算法适用于较小的数。但是如果这个数有100位，这个程序需要执行的运算次数会达到50位。即使是最快的计算机也不能在合理的时间内完成如此多的运算。（一台每秒运算1万亿次的计算机需要用3×1030年来完成这个运算。）
一些加密算法需要使用大素数，因此这种检验某数是否为素数的方法将无法有效工作。幸运的是还有其他方法。费马素性测试就是其中一种较简单的方法。
费马小定理表明如果p是素数，并且1≤n≤p，np-1 Mod p＝1。换句话说，如果将p-1个n相乘，再用所得的数除以p，结果为1.
例如，假设p＝11，n＝2，那么np-1 Mod p＝210 Mod 11＝1 024 Mod 111 024＝11×93＋1，因此1 024 Mod 11＝1。
请注意即使p不是素数，np-1 Mod p＝1也可能成立。在这种情况下n被称作费马骗子（Fermat liar）。因为它错误地暗示了p是素数。
如果np-1 Mod p≠1，那么n被称作费马证人（Fermat witness）。因为n证明了p不是素数。
可以证明，对于自然数p，至少1和p中的一半数n是费马证人。也就是说，如果p不是素数，并且如果随机抽取了1和p中的一个数n，有50%的可能性n是一个费马证人，因此np-1 Mod p≠1。
当然，也有时候会不走运，随机选择的一个n是费马骗子。如果重复试验进行多次，可以增加能够选择到一个费马证人的机会，当然前提是它存在的话。
可以看出，在每个测试中有50％的机会，选择到一个费马证人。所以，如果p通过k
次测试，那么就有的机会每次都得到费马骗子。换句话说，有的机会p实际上是
一个合数却假装是素数。
例如，如果p通过测试10次，就有1/210≈0.000 98概率为p不是素数。如果想更加肯定，重复测试100次。如果p通过了所有的100个项目，就只有1/2100≈7.8×10-31概率证p不是素数。
下面的伪代码描述了使用此方法来确定一个数是否可能是素数的算法：
注 这是一个概率算法（一个产生正确结果有一定的概率的算法）的例子。
目前仍然有一个很小的可能性证明该算法是错误的，但可以重复测试直到达到想要的任何确定性级别。
有一种情况会使这整个问题变得相当有趣，那就是如果数p是非常大的，计算NP-1使用乘法可能需要相当长的时间。
幸运的是，我们已经知道如何通过快速求幂做到这一点，算法参见2.3节中所描述的“执行幂”。
一旦我们知道了如何判断一个数是否（可能）是素数，就可以写一个算法来选择素数：