测试素数比执行整数分解要容易得多。

有几种方法可以测试素数，例如确定性埃拉托色尼筛法和概率米勒-拉宾素数检验。OpenSSL 使用几个测试来检查素数。首先，他们对数字进行确定性检查，尝试用多个小素数除候选，然后进行一系列米勒-拉宾素数测试。绝大多数候选素数在第一次素数测试中就被丢弃了。任何通过考试的候选人都将接受进一步的测试，每轮测试都会增加它是素数的确定性。

使用 Miller-Rabin 检验时，合数在每一轮中被检测到的几率为 75%，因此在仅仅 64 轮测试之后，合数未被检测到的概率是惊人的 2 ^-128。换句话说，测试有 4 ^-n的假阴性机会，其中n是测试轮数。还有许多慢得多的方法来测试一个数字是否是完全确定的素数，例如Agrawal-Kayal-Saxena 素数测试，但出于密码学目的，真的、真的确定就足够了，所以它们往往不是用过的。

默认情况下，OpenSSL 往往会更加偏执，并会进行一些其他测试，特别是针对安全的素数。因此，当找到素数p时，它还会检查(p - 1) / 2是否为素数。这对于素数的特定应用很重要，例如 Diffie-Hellman，其中安全素数可以防止某些攻击。

这可能是在一个较高的速度，因为验证一个整数是错误的非常低毛利率的黄金比保理它显著容易，因为素数是不是那罕见（很容易通过增加一个发现大量的素数数和素数测试）。Miller-Rabin 素数检验非常有效。如果x ^{n - 1} ≢ 1 (mod n)（费马测试），并且通过测试x ^{(n - 1) / 2 e} (mod n)是否是1 mod n的非平凡平方根，则该测试证明了复合性，其中n是被测试的整数，x是随机数见证满足区间1 < x < n。

取自 Wikipedia 的测试的伪代码实现是：

输入：n > 3，要测试素数的奇数；
       k，决定测试准确度的参数
输出：如果 n 是合数，则为合数，否则可能是素数

将 n - 1 写为 2 r ·d ，其中 d 为奇数，通过从 n - 1 分解 2 的幂
WitnessLoop：重复k次：
    在 [2, n - 2] 范围内选择随机整数 a
    x ← a d mod n
    如果 x = 1 或 x = n - 1 那么
        继续见证循环
    重复 r - 1 次：
        x ← x 2 mod n
        如果 x = 1 那么
            返回复合
        如果 x = n - 1 那么
            继续见证循环
    返回复合
返回可能是素数

请参阅有关 RSA 密钥生成和FIPS 186-4标准的Crypto.SE 答案，第 5.1 节。