生成 Diffie-hellman 参数（生成器）
Generating Diffie-hellman parameters (generator)
我正在尝试实施 diffie-hellman 密钥交换。假设我找到了一个大质数 p - 我怎样才能找到生成器 g?
受限于必须使用的多精度库，只有几个基本操作(+, *, -, /, pow, modExp, modMult, mod, gcd, isPrime, genRandomPrime, genRandomBits, and a few of a more) are available.
寻找一个安全素数 q 是否可行，以便 gcd(n,q) == 1 对应的每个数字 n一台发电机，对吧？
你基本上回答了你的问题。只是测试 gcd(n,q)==1 是不必要的，因为 q 是质数。这意味着任何数字 n，使得 n < q 与 q 没有公因数并且 gcd(n,q) 将始终输出 1。
你可以检查q=2p + 1是否是质数。如果是这样，那么 ord(Zq) = q-1 = (2p+1)-1 = 2p。由于 ord(x) | ord(Zq) 对于 Zq 中的每个 x ord(x)=2或 ord(x)=p 或 ord(x)=2p。因此，您只需要检查从 {2,...,q-1} 中随机选择的元素 x 是否为 2 阶。如果不是，则它为 p 或 2p 阶，并且你可以将它用作发电机。
通常，不要向程序员询问有关密码学的问题。密码学是微妙的，因此以不可见的方式很困难，很容易导致对自己能力的自欺欺人。相反，请询问密码学家（其中许多也是程序员）。 Stack Exchange 有一个加密板，这个问题已经在其中得到了解答。
https://crypto.stackexchange.com/questions/29926/what-diffie-hellman-parameters-should-i-use
我可以对那里的建议提出异议，但它基本上是正确的。除非你真的想学习相关的数学，否则我会服从权威；上面的答案中引用了它们。
关于你问的数学题，这里稍微介绍一下。对质数 p 取模的乘法群的大小为 p-1。 （见Fermat's Little Theorem.) The order of any element必须除p-1。最有利的情况是p-1=2q，其中q也是素数。
如果你非常关心你的安全，你已经得到了不要推出自己的加密货币的仪式告诫，所以这里是如何找到一个生成器 mod 一个安全的素数 q。当且仅当 g^((q-1)/2) != 1 mod q 时，闭域 [2, q - 2] 中的数字 g 是生成器，您应该使用标准算法计算它用于 mod 平方幂。选择 g 的随机值，直到一个通过测试。
我正在尝试实施 diffie-hellman 密钥交换。假设我找到了一个大质数 p - 我怎样才能找到生成器 g?
受限于必须使用的多精度库，只有几个基本操作(+, *, -, /, pow, modExp, modMult, mod, gcd, isPrime, genRandomPrime, genRandomBits, and a few of a more) are available.
寻找一个安全素数 q 是否可行，以便 gcd(n,q) == 1 对应的每个数字 n一台发电机，对吧？
你基本上回答了你的问题。只是测试 gcd(n,q)==1 是不必要的，因为 q 是质数。这意味着任何数字 n，使得 n < q 与 q 没有公因数并且 gcd(n,q) 将始终输出 1。
你可以检查q=2p + 1是否是质数。如果是这样，那么 ord(Zq) = q-1 = (2p+1)-1 = 2p。由于 ord(x) | ord(Zq) 对于 Zq 中的每个 x ord(x)=2或 ord(x)=p 或 ord(x)=2p。因此，您只需要检查从 {2,...,q-1} 中随机选择的元素 x 是否为 2 阶。如果不是，则它为 p 或 2p 阶，并且你可以将它用作发电机。
通常，不要向程序员询问有关密码学的问题。密码学是微妙的，因此以不可见的方式很困难，很容易导致对自己能力的自欺欺人。相反，请询问密码学家（其中许多也是程序员）。 Stack Exchange 有一个加密板，这个问题已经在其中得到了解答。
https://crypto.stackexchange.com/questions/29926/what-diffie-hellman-parameters-should-i-use
我可以对那里的建议提出异议，但它基本上是正确的。除非你真的想学习相关的数学，否则我会服从权威；上面的答案中引用了它们。
关于你问的数学题，这里稍微介绍一下。对质数 p 取模的乘法群的大小为 p-1。 （见Fermat's Little Theorem.) The order of any element必须除p-1。最有利的情况是p-1=2q，其中q也是素数。
如果你非常关心你的安全，你已经得到了不要推出自己的加密货币的仪式告诫，所以这里是如何找到一个生成器 mod 一个安全的素数 q。当且仅当 g^((q-1)/2) != 1 mod q 时，闭域 [2, q - 2] 中的数字 g 是生成器，您应该使用标准算法计算它用于 mod 平方幂。选择 g 的随机值，直到一个通过测试。