Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. 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

For my cryptography class project in university I have selected Paillier Cryptosystem as a course project

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.


share|improve this question
up vote 4 down vote accepted

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.

share|improve this answer
thanks alot, what about the other part of the question? do you have any clue? – zzlalani Apr 13 '14 at 19:45
like how can I find μ – zzlalani Apr 13 '14 at 19:48
@zzlalani added more on that. – DrLecter Apr 13 '14 at 20:03
If I remember correctly, $g=n+1$ fulfills the necessary condition and is a viable option if you don't need a random generator. – tylo Apr 14 '14 at 12:15
@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. – DrLecter Apr 24 '14 at 17:56

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.