How to find g in Factoring-Based Trapdoor Hash Function 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
$n=p*q$
$\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