cryptography - 快速查找 Schnorr 群生成器的方法

Question

要找到Schnorr 群生成器，我必须找到三个数字 p、q 和 r，这样：

• p = qr + 1
• p 和 q 是素数

当 p 和 q 应该是非常大的素数时，很难找到满足所有标准的 q 和 r。我尝试使用 GNU GMP 库随机查找 q 和 r，但我在笔记本电脑上的 30 分钟内没有找到符合上述标准的数字。

有没有什么快速的方法可以找到这样的数字和 Schorr 群生成器？

谢谢！

Answer 1

我在当前 DSA 规范的 A1.1.2 章中找到了这种方法。

所描述的方法的要点是

1. 选择素数q；
2. 选择一个较大的值X（与期望的大小大致相同p）；
3. 计算p = X - (X mod 2q) + 1（即现在p = 1 (mod 2q)）；
4. 检查是否p是素数。