# 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.

• 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 – D balaji Aug 24 '16 at 7:26
• @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? – poncho Aug 24 '16 at 12:35