Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

Use the following fact: If in a group we have $a^n=1$, then the order of $a$ must be a factor of $n$ (possibly trivial).

The group $G=\mathbb{Z}_{p^2}^*$ is cyclic of order $p(p-1)$. So if $g\in G$, we always have $g^{p(p-1)}=1$. Therefore $g_p^p=1$ for all $g\in G$. This means that the order of $g_p$ is a factor of $p$. As $p$ is a prime, the order must be either $1$ or $p$. Therefore we only need to check the possibility $a=1$. IOW, if $g_p\neq1$ in $G$, then $g_p$ must have order $p$.

Note: You cannot pick any random integer $g<n$. You must first check that $g$ is not divisible by $p$. Otherwise $g\notin G$.

share|cite|improve this answer
Now that's what I call a good answer! Thank you very much Jyrki. – Mihai Todor May 31 '12 at 12:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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