For my cryptography class project in university I have selected Paillier Cryptosystem as a course project http://en.wikipedia.org/wiki/Paillier_cryptosystem#Key_generation

In key generation it says

Choose two large prime numbers $p$ and $q$

I have selected $p$ = 11 and $q$ = 17, it also satisfies the condition

$gcd(pq, (p-1)(q-1))=1$

which makes my $n$ = 187 and ${\lambda}$ = 80

and now in 3rd point it says

Select random integer $g$ where $g \in (\mathbb{Z}_n^∗)^2$

now what does it mean $g \in (\mathbb{Z}_n^∗)^2$?

there is a question What does $(\mathbb{Z}_n^*)^2$ mean? but it doesn't make any sense to me

so the first question is how can I select the random integer g?

In 4th point it says

Ensure $n$ divides the order of $g$ by checking the existence of the following modular multiplicative inverse: $\mu\ = (L(g^{\lambda}\mod n^{2}))^{-1} \mod n$

it further says

where function $L$ is defined as $L(u) = \frac{u-1}{n}$ .

can some one please help me to find out $g$ and $\mu$?

  • The public (encryption) key is $(n, g)$.
  • The private (decryption) key is $(\lambda, \mu)$.

with any example or link that can guide me to a correct path.



1 Answer 1


The requirement is that your element $g$ is in $\mathbb{Z}_{n^2}^*$ and not in $(\mathbb{Z}_{n}^*)^2$.

The set $\mathbb{Z}_{n^2}^*$ is the set of integers smaller than $n^2$ that are relatively prime to $n^2$, i.e., you require an element $g$ from $\mathbb{Z}_{n^2}$ such that $\gcd(g,n^2)=1$.

$(\mathbb{Z}_{n}^*)^2$ on the other hand is the set of pairs $(a,b)$ such that $a$ and $b$ are from $\mathbb{Z}_n^*$.

You compute $\lambda=lcm(p-1,q-1)$ where $lcm$ is the least common multiple. Then for your chosen $g$ you have to check whether $a=L(g^\lambda \bmod n^2)$ (where $L(u)=\frac{u-1}{n}$ ) has a multiplicative inverse modulo $n$ (is an element in $\mathbb{Z}_n^*$), i.e., you have to check whether $\gcd(a,n)=1$. If this is the case, then compute $\mu$ as $a^{-1} \bmod n$. Otherwise, try with another $g$ until this condition is satisfied.

  • $\begingroup$ thanks alot, what about the other part of the question? do you have any clue? $\endgroup$
    – zzlalani
    Apr 13, 2014 at 19:45
  • $\begingroup$ like how can I find μ $\endgroup$
    – zzlalani
    Apr 13, 2014 at 19:48
  • 4
    $\begingroup$ If I remember correctly, $g=n+1$ fulfills the necessary condition and is a viable option if you don't need a random generator. $\endgroup$
    – tylo
    Apr 14, 2014 at 12:15
  • 1
    $\begingroup$ @tylo, yes that's correct. at the cost of a larger $\lambda$ ($\varphi(n)$ instead of $lcm(p-1,q-1)$). $\endgroup$
    – DrLecter
    Apr 14, 2014 at 12:19
  • 1
    $\begingroup$ @zzlalani first, your $r$ is not co-prime to $n$, lets take $r=3$. Then your ciphertext is 1062. I'm not sure if your inverse is correct. You have to compute inverses in the ring modulo $n$, i.e., $24^{-1}$ should be 19 (an inverse $x^{-1}$ of $x$ modulo $n$ is defined such that $x\cdot x^{-1} \equiv 1 \pmod n$). Then decrypting $1062$ yields $4$, which is correct. $\endgroup$
    – DrLecter
    Apr 24, 2014 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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