1
$\begingroup$

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.

1 Answers 1

4

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. You must first check that $g$ is not divisible by $p$. Otherwise $g\notin G$.

  • 0
    Now that's what I call a good answer! Thank you very much Jyrki.2012-05-31