Please explain how to find a value of $g$ if
$p,q$ are safe primes having $p'=(p-1)/2$ and $q'=(q-1)/2$ are also primes
$\lambda(𝑛) = \operatorname{lcm}(𝑝 − 1, 𝑞 − 1) = 2𝑝'𝑞'$.
How to chose at random an element $g$ of order $\lambda(𝑛)$?


There are several different ways to do this:

  • The most obvious way to do this, if you know $p$ and $q$, is to select random values $r$ relatively prime to $n$, and determine their order; that is, verify that none of $r^{\lambda(x)/(p-1)}, r^{\lambda(x)/(q-1)}, r^{\lambda(x)/2}$ are 1. Since approximately three quarters of possible $r$ values do have order $\lambda(n)$, this is efficient (if not as efficient as the methods I show below).

However, this doesn't work if either you yourself don't know the factorization of $n$, or you need to demonstrate to someone else know doesn't know.

$t$ has order $\lambda(n)$ if $t, t-1, t+1$ are all relatively prime to $n$, and if $t$ is either a quadratic nonresidue mod p, or a quadratic nonresidue mod q (or both).

  • The easiest way to select such a $t$ is to go with the 'both' option; select a random $r$ and set $t = -r^2 \bmod n$ (and verify that $t+1$ is relatively prime to $n$); $r^2$ is a quadratic residue mod p (obviously), and as $p \equiv 3 \pmod 4$, if $r^2$ is a quadratic residue, $-r^2$ must be a quadratic nonresidue (and similarly for $q$). And, if we select $r$ to be a nothing-up-my-sleeve number, so is $t$. The only downside is that this process will generate only a third of the potential values.

  • Another approach is to select random $t$ values (where $t-1, t+1$ are relatively prime to $n$), and compute the [Jacobi symbol][1] to $t$ with respect to $n$; if it is -1, then we know that $t$ is a quadratic residue to one of $p, q$, and a quadratic nonresidue to the other; we don't know which, but in this case, we don't care. Approximately half of the possible $t$ values will have a -1 Jacobi value and so this is also reasonably efficent (if a bit more work, in part because libraries that can compute the Jacobi symbol are a tad more rare). And, this method will generate the two-thirds potential values that the previous method does not.

And, if it is critical that we generate a value which is strictly uniform (even if you don't know $p$ and $q$), you can use the $-r^2$ method with probability 1/3, and the Jacobi method with probability 2/3; that turns out to generate all possible values with uniform probability.

[1] https://en.wikipedia.org/wiki/Jacobi_symbol

  • $\begingroup$ thank you poncho!!! I am getting the value of g but if I use prime no p and q of size 512 then it is taking too much time ! can you guide me how to minimize the complexity. Thank you once again $\endgroup$ – D balaji Aug 24 '16 at 7:26
  • $\begingroup$ @Dbalaji: I gave you three separate methods for doing so; what's taking too long? Or, is it using $g$ (which you never discussed in your question) which is taking too long? $\endgroup$ – poncho Aug 24 '16 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.