1
$\begingroup$

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$).

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ How about a link to the paper? Is it about cryptography? $\endgroup$
    – Barack Obama
    Commented May 7, 2013 at 20:59
  • 2
    $\begingroup$ 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. $\endgroup$
    – Maeher
    Commented May 7, 2013 at 21:30
  • 2
    $\begingroup$ 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^*$. $\endgroup$
    – Dilip Sarwate
    Commented May 7, 2013 at 21:31
  • 1
    $\begingroup$ The multiplicative group would only be $\:\{1,2,...,n-1\}\:$ when $n$ is prime. $\hspace{1 in}$ $\endgroup$
    – user991
    Commented May 7, 2013 at 21:36
  • $\begingroup$ @RickyDemer Thanks for catching that. Unfortunately, it is too late to edit my comment. $\endgroup$
    – Dilip Sarwate
    Commented May 7, 2013 at 21:47

1 Answer 1

Reset to default
3
$\begingroup$

$\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.

Improve this answer
$\endgroup$
14
  • 1
    $\begingroup$ The integers modulo $n$ (excluding zero) are not necessarily a group under multiplication. $\hspace{.58 in}$ $\endgroup$
    – user991
    Commented May 7, 2013 at 21:53
  • $\begingroup$ 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\}\:$. $\;\;$ $\endgroup$
    – user991
    Commented May 8, 2013 at 2:22
  • $\begingroup$ @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. $\endgroup$
    – Henrick Hellström
    Commented May 8, 2013 at 2:40
  • 1
    $\begingroup$ @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! $\endgroup$
    – user4811
    Commented May 8, 2013 at 13:17
  • 1
    $\begingroup$ @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. $\endgroup$
    – minar
    Commented Jul 18, 2013 at 13:29

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.