For a school project I'm implementing these Paillier performance improvements. In chapter 2.2 Scheme 3 subsection Key Generation and Secure Choice of Parameters there are remarks on how to efficiently generate parameter $\alpha$:
The DSA key generation applied twice produces $g_1$ of order $\alpha_1$ in $\Bbb Z^∗_p$ and $g_2$ of order $\alpha_2$ in $\Bbb Z^∗_q$, respectively. As next step, we interpret $g_1$ and $g_2$ as elements in $\Bbb Z^∗_{p^2}$ and $\Bbb Z^∗_{q^2}$ , respectively. It is straight-forward to check whether the order of $g_1$ in $\Bbb Z^∗_{p^2}$ is $\alpha_1p$ and the order of $g_2$ in $\Bbb Z^∗_{q^2}$ is $\alpha_2q$ indeed. (In our experiments with the OpenSSL DSA key generation, this was always the case.) One then finds $g$ of order $\alpha_1\alpha_2pq$ = $\alpha n$ in $\Bbb Z^∗_{p^2q^2}$ = $\Bbb Z^∗_{n^2}$ by using the Chinese Remainder Theorem. As can be easily checked, α is indeed a divisor of λ.
(Please note that $n = p\times q$)
Variables I know values of (generated by DSA cryptosystem): $\{n, p, q, g_1, g_2, \alpha_1, \alpha_2\}$
So far I understand that:
"$g_1$ of order $\alpha_1$ in $\Bbb Z^∗_p$" $\implies g_1^{\alpha_1} \equiv 1 \pmod p$
"$g_2$ of order $\alpha_2$ in $\Bbb Z^∗_q$" $\implies g_2^{\alpha_2} \equiv 1 \pmod q$
Following the text:
"$g_1$ of order $\alpha_1p$ in $\Bbb Z^∗_{p^2}$" $\implies g_1^{\alpha_1p} \equiv 1 \pmod {p^2}$
"$g_2$ of order $\alpha_2q$ in $\Bbb Z^∗_{q^2}$" $\implies g_2^{\alpha_2q} \equiv 1 \pmod {q^2}$
The task is:
Find $g$ of order $\alpha_1\alpha_2pq$ = $\alpha n$ in $\Bbb Z^∗_{p^2q^2}$ = $\Bbb Z^∗_{n^2}$ by using the Chinese Remainder Theorem.
How can I reorganise those equations to compute $g$ using CRT? Or should I approach to the problem differently?
Thank you, Muzosh.