cryptography - 寻找 20 位素数的生成器 g 我是 Elgamal

Question

我很想知道是否有一种简单的方法/算法，通过它我可以获得 20 位素数的生成器 g 以在 Elgamal 密码系统中实现。

Answer 1

最好的方法是选择您的素数，以便轻松找到发电机。通常最好的方法是找到一个素数 p 使得 q=2p+1 也是素数。那么在q阶的乘法群中，元素的阶数为2p、p、2或1。大多数的阶数为2p，所以只需选择一个数字g并检查g^2和g^p是否不是1，那么它会有 2p 的顺序，因此是该组的生成器。

如果给定素数（比如 q），那么组的顺序将是 q-1，您需要将 q-1 分解为素数（这并不总是容易的）。然后在选择候选 g 时，您需要检查 g^x（对于 x 范围内小于 q-1 的素因子的所有组合）不是 1，然后您就会知道 g 具有顺序 q-1 和是一个发电机。这就是为什么，如果您可以选择素数 q，则更容易确保 q-1 很好地分解为两个素数。