求Schnorr群生成器的快速方法

Question

要找到Schnorr群发生器，我必须找到三个数字p、q和r，以便：

• P= qr +1
• P和Q是素数

当p和q应该是很大的素数时，很难找到满足所有准则的q和r。我尝试使用GNU库随机查找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是否为素数。