cryptography - シュノール群生成子を高速に見つける方法

Question

シュノール群生成子を見つけるには、次のような 3 つの数 p、q、r を見つける必要があります。

• p = qr + 1
• p と q は素数

p と q が非常に大きな素数でなければならない場合、すべての基準を満たす q と r を見つけることは非常に困難です。GNU GMP ライブラリを使用して q と r をランダムに見つけようとしましたが、ラップトップで 30 分間見つけた数字で上記の基準を満たすものはありませんでした。

そのような数とショール群ジェネレーターを見つけるための高速な方法はありますか?

ありがとう！

Answer 1

そのような方法は、現在のDSA仕様のA1.1.2章で見つけました。

説明されている方法の要点は

1. プライムを選ぶq;
2. 大きな値を選択しますX（目的のサイズとほぼ同じサイズp）。
3. 計算p = X - (X mod 2q) + 1（つまり、今p = 1 (mod 2q)）;
4. pが素数であるかどうかを確認します。