# What does $(\mathbb{Z}_n^*)^2$ mean?

In a paper they write once, $(\mathbb{Z}_n^*)^2$. Is this the group of quadratic residues or is it something else?

Here the theorem:

Under the strong RSA assumption, given a modulus $n$, along with random elements $g, h \in (\mathbb{Z}_n^∗)^2$, it is hard to compute $w \in \mathbb{Z}_n^*$ and integers $a, b, c$ such that $w^c = g^a h^b$ and ($c \nmid a$ or $c \nmid b$).

-
How about a link to the paper? Is it about cryptography? –  Barack Obama May 7 '13 at 20:59
It could mean $\mathbb{Z}_n^*\times \mathbb{Z}_n^*$, i.e., the set of pairs of elements from $\mathbb{Z}_n^*$. A little bit of context might help. –  Maeher May 7 '13 at 21:30
Typically, $\mathbb Z_n^*$ would mean the multiplicative group of the ring $\mathbb Z_n$, the set of integers $\{0,1,2,\ldots, n-1\}$ with arithmetic being done modulo $n$. The multiplicative group would, of course, be $\{1,2,\ldots, n-1\}$ with multiplication being done modulo $n$. I would suspect that $(\mathbb{Z}_n^*)^2$ is the Cartesian product $\mathbb{Z}_n^*\times \mathbb{Z}_n^*$ whose elements are of the form $(a,b)$ with $a, b \in \mathbb{Z}_n^*$. –  Dilip Sarwate May 7 '13 at 21:31
The multiplicative group would only be $\:\{1,2,...,n-1\}\:$ when $n$ is prime. $\hspace{1 in}$ –  Ricky Demer May 7 '13 at 21:36
@RickyDemer Thanks for catching that. Unfortunately, it is too late to edit my comment. –  Dilip Sarwate May 7 '13 at 21:47

$\mathbb Z_n^*$ is a mathematical notation for the multiplicative group of integers modulo $n$. In other words, it is the set of integers that are relatively prime to $n$, all taken modulo $n$ (excluding zero). The $*$ symbol is commonly used for denoting "the set of elements in the multiplicative group", which in this case means "the set of elements that are relatively prime to $n$".

Normally $\mathbb Z_n^*$ is treated as a multiplicative group, so it comes coupled with the multiplication operation modulo $n$. (In contrast $\mathbb Z_n$ would denote the group of integers modulo $n$ under addition, or the field over the same set with both addition and multiplication.)

When such algebraic structures are raised to the power of two, it is an abbreviation for the Cartesian product of the underlying set with itself, in this case $\mathbb Z_n^* \times\mathbb Z_n^*$, i.e. the set of value pairs $(x,y)$ where both $x,y$ are integers in the range $1$ to $n-1$ and relatively prime to $n$.

Cartesian products of sets are also sets and might be coupled with one or more binary operations to form algebraic structures, such as fields and groups. In this case, the operations would be determined by context.

Edit: It should be noted that in mathematics, the $*$ symbol is more generally used for denoting a set excluding element zero. For instance, $\mathbb Z^*$ means the set of integers except $0$. However, it doesn't make sense to extrapolate this notation to finite sets such as $\mathbb Z_n^*$, except when $n$ is prime. If $n$ is composite, the set of integers $1$ to $n-1$ is not closed under multiplication, but the set of integers relatively prime to $n$ is. Hence, it is usually safe to presume $\mathbb Z_n^*$ denotes the (underlying set of the) multiplicative subgroup, unless explicitly stated otherwise.

-
The integers modulo $n$ (excluding zero) are not necessarily a group under multiplication. $\hspace{.58 in}$ –  Ricky Demer May 7 '13 at 21:53
I've always seen $\mathbb{Z}_n^*$ as the group of units modulo $n$, even when that is not equal to $\:\mathbb{Z}_n-\{0\}\:$. $\;\;$ –  Ricky Demer May 8 '13 at 2:22
@RickyDemer: Me too, but I consulted my text books in mathematics. The * symbol means "excluding zero", and does not necessarily entail that all elements are invertible under the implied operation. For instance, $(\mathbb Z^*,\cdot)$ means the set of non-zero integers under multiplication, which has all properties of a group except invertibility. I don't know what is the correct way of denoting the subgroup of integers relatively prime to the modulus. –  Henrick Hellström May 8 '13 at 2:40
@HenrickHellström: I have looked a little bit around. The theorem was copied from another paper. In the original paper they have never used quadratic residues but Cartesian products. It makes all sense now! Thanks a lot for your help! –  user4811 May 8 '13 at 13:17
@HenrickHellström: For a ring $R$, the notation $R^*$ denotes $R$ minus the divisors of zero. Recall that $x$ is a divisor of zero in $R$ iff there exists a non-zero element $y$ in $R$ such that $xy=0$. With this definition, all the special cases mentionned above such as $\mathbb{Z}_n$ or $\mathbb{Z}_1$ are also accounted for. –  minar Jul 18 '13 at 13:29