0

We have $g^k = 1$ for every $g \in Z_N^\ast$, and therefore $g^{k/2}$ is a square root of unity modulo $N$.
–Dan Boneh, "Twenty Years of Attacks on the RSA Cryptosystem"

In this statement, what does $Z_N^\ast$ represent?

It's clear (I think, but could be wrong,) that subscript-$N$ means that it's the integers modulo $N$, but it seems unlikely that the superscript asterisk has its usual meaning of "an infinite string of" in this context; I don't even have an idea of what to make of it.

(Per comments, it looks like this was, in part, a typesetting mistake—the author almost certainly intended to write $\Bbb{Z}_N^\times$—though the question remains essentially as-stated.)

JamesTheAwesomeDude
  • 235
  • 1
    I'm guessing it's used to refer to nonzero integers modulo $N$. – Sean Roberson Jul 20 '22 at 16:18
  • 5
    ${1,2,3\cdots,N-1}$, it refers to the invertible elements mod N – L F Jul 20 '22 at 16:22
  • 8
    Given a ring $(R,+,\cdot)$, $R^*$ is the multiplicative group of its invertible elements (i.e. the elements $x\in R$ such that there is some $y\in R$ such that $xy=yx=1$). For $R=\Bbb Z_N$, you can equally take it as the set of the elements $x\in{0,\cdots, N-1}$ such that $\operatorname{gcd}(N,x)=1$ endowed with multiplication modulo $N$. – Sassatelli Giulio Jul 20 '22 at 16:26
  • 2
    https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n – Karl Jul 20 '22 at 17:41
  • @emacsdrivesmenuts Thanks for the edit suggestion, but I think the author didn't use Blackboard typesetting. – JamesTheAwesomeDude Jul 20 '22 at 18:10
  • @JamesTheAwesomeDude. I checked the linked PDF and it uses $\Bbb Z$ (something like \Bbb Z in LaTeX speek). – emacs drives me nuts Jul 20 '22 at 18:13
  • @emacsdrivesmenuts Per my screenshot, the bit I quoted is typeset non-Blackboard, and that was part of the reason I lacked confidence in my interpretation of the symbol. I would welcome a criticism of Dan Boneh's inconsistency in an Answer, however, as he appears to use the Blackboard font for the same(?) symbol elsewhere in the document. – JamesTheAwesomeDude Jul 20 '22 at 18:17
  • @JamesTheAwesomeDude: Ok, I didn't check each and every occurrence of "Z" in that document; sorry for the noise. – emacs drives me nuts Jul 20 '22 at 18:19
  • 2
    @emacsdrivesmenuts Honestly, it'd be great for an answer to nitpick the typesetting of the original document from a knowledgeable perspective -- the author's use of $\ast$ instead of $\times$ in that symbol was another obstacle to identifying it -- even if I'd stumbled across the appropriate Wikipedia page, I might have not matched it due to that. – JamesTheAwesomeDude Jul 20 '22 at 18:20
  • @JamesTheAwesomeDude $R^*$ is just as common a notation as $R^\times$ for the group of units. – Sassatelli Giulio Jul 20 '22 at 20:56

1 Answers1

1

$\mathbb{Z}_N^\times$ refers to the multiplicative group of integers modulo $N$.

In other words: those elements of ring $\mathbb{Z}_N$ which are invertible under $\times$.

In other words: the nonnegative integers less than $N$ which are coprime to $N$.

In other words: for prime $N$, $\mathbb{Z}_N \setminus {\{{0}\}}$ — the positive integers less than $N$.

Beware that some authors may use $\ast$ or $\cdot$ instead of $\times$!

JamesTheAwesomeDude
  • 235