我正在为 Diffie-Hellman 类型的密钥 p 生成一个 2048 位安全素数，使得 p 和 (p-1)/2 都是素数。
我可以在 p 和 (p-1)/2 上使用多少次 Rabin-Miller 迭代，并且仍然对加密强密钥充满信心？在我所做的研究中，我听说过 1024 位普通素数的 6 到 64 次迭代，所以在这一点上我有点困惑。一旦确定了，如果你生成的是一个安全的素数而不是一个普通的素数，这个数字会改变吗？
计算时间非常宝贵，所以这是一个实际问题——我基本上想知道如何找出我可以摆脱的尽可能少的测试，同时保持几乎有保证的安全性。
我刚刚在stackoverflow上回答了同样的问题，所以我将在这里复制我的答案（我不认为重复是要走的路；也许应该迁移这个问题）：
让我们假设您通过选择随机值来选择一个素数p，直到您找到一个 Miller-Rabin 所说的：那个看起来像一个素数。Miller-Rabin 测试最多使用n轮。（对于所谓的“安全素数”，除了运行两个嵌套测试之外，事情没有改变。）
一个随机的 1024 位整数是素数的概率约为 1/900。现在，您不想做任何愚蠢的事情，因此您只生成奇数值（偶数 1024 位整数保证非素数），并且更一般地说，仅当该值不是“明显" 非素数，即可以被一个小素数整除。因此，在达到素数（平均）之前，您最终会使用 Miller-Rabin 尝试大约 300 个值。当该值是非质数时，Miller-Rabin 将在每轮以 3/4 的概率检测到它，因此对于单个非质数，您将运行的 Miller-Rabin 轮数平均为 1+(1/4 )+(1/16)+... = 4/3。对于 300 个值，这意味着大约 400 轮 Miller-Rabin，无论您为n选择什么。
（编辑：实际上，对于随机选择的非素数，Miller-Rabin 的效果比这更好（参见@Brett 的回答），平均轮数将接近 300 次而不是 400 次。它并没有显着改变我的论点。）
因此，如果您选择n为例如 40，则n隐含的成本小于总计算成本的 10%。随机素数选择过程由对非素数的测试控制，这些测试不受您选择的n值的影响。我在这里谈到了 1024 位整数；对于更大的数字，n的选择就更不重要了，因为随着大小的增加，素数变得越来越稀疏（对于 2048 位整数，上面的“10%”变成“5%”）。
因此，您可以选择n=40并对此感到满意（或者至少知道减少n无论如何都不会给您带来太多好处）。另一方面，使用大于 40 的n是没有意义的，因为这会使您获得的概率低于简单计算错误的风险。计算机是硬件，它们可能会出现随机故障。例如，素数测试函数可以为非素数返回“真”，因为宇宙射线（一种高速穿过宇宙的高能粒子）碰巧在正确的时间击中了正确的晶体管，翻转了返回值从 0（“假”）到 1（“真”）。这是非常不可能的——但不亚于概率2 -80。看到这个stackoverflow答案了解更多详情。底线是，无论您如何确保整数是素数，您仍然有一个不可避免的概率元素，并且 40 轮 Miller-Rabin 已经为您提供了您所希望的最佳结果。
总而言之，使用 40 发子弹。
对于 p(1024, t) < (2^-80)，完全不需要( t = 40 ) 随机基数的 MR 迭代。不超过 1/4 的复合奇数值是随机基数的 SPRP。((1/4)^t) 是极其悲观的，论文DLP , RBJ（后者也证明了 DLP 猜想：p(k, t) < (1/4)^t, for k >= 2, t >= 1)，结合证明 ( t = 3 ) 次迭代足以产生的结果：p(1024, t) < 2^-80. 另见：应用密码学手册第 4 章，表 4.4。这个相同的 ( t = 3 ) 值用于 OpenSSL 库中的 1024 位值。
20190202：我决定根据这些论文添加指向我自己的代码的链接。虽然mrtab实用程序是关键，但它所构建的 LUT 和断言测试程序都是包的一部分。我总是很感激有关该mrtab项目的任何反馈。
加快米勒拉宾速度的最重要因素是首先对一组小素数进行简单的整除性测试，如果通过，则仅使用米勒拉宾。
如果一个随机的 k 位奇数 n 可以被一个小素数整除，那么通过试除法排除候选 n 的计算成本比使用 Miller-Rabin 检验要低。由于随机整数 n 具有较小素因数的概率较大，因此在应用 Miller-Rabin 检验之前，应测试候选 n 是否存在低于预定界限 B 的小因数。”