Here is what I have:
- select $p$ such that $p - 1$ has a large prime factor $t$: $p - 1 = tu$, where $u$ is a random number
- $n = p^2 q$, where $q$ is prime
- pick random $g < n$ and compute $g_p = g^{p - 1} \pmod {p^2}$ until $g_p$ is of order $p$ in $\mathbb{Z}_{p^2}^*$
My question is how do I ensure that $g_p$ has order $p$ in $\mathbb{Z}_{p^2}^*$? If I test $g_p^p \pmod {p^2} = 1$, then does this guarantee that \forall a < p, $g_p^a \pmod {p^2} \neq 1$?
I tried to apply Algorithm 4.79 from the Handbook of Applied Cryptography, chapter 4 for determining the order of a group element, but it seems to break to pieces for the particular case of $n = p^2 q$...
For completeness, this procedure is required by the Okamoto-Uchiyama cryptosystem, as described in the "Accelerating Okamoto-Uchiyama's Public-Key Cryptosystem" paper.