Score:3

problem with a discrete logarithm/cyclic groups example... can anyone clarify this concept for me?

in flag

I was watching this really short video about the discrete logarithm example: https://www.youtube.com/watch?v=SL7J8hPKEWY and at 0:38 they show all the possible values that you can get if $p = 17$ and $g = 3$. At 1:00 they state that the solution is equally likely to be any integer between 1 and 17.

My questios are;

  • What about $0$? From what I learned about cyclic groups, $17 \bmod 17$ is just $0$. I suppose they meant a number between $0$ and $16$ then, but... why isn't the $3^x = 0 \bmod 17$ shown in the video then?

  • If $3$ is really a primitive root of 17, a.k.a, a generator, that value of $x$ should exist, right? Or am I missing something?

  • If $p = 17$, shouldn't the order of the group be equal to $17$ too? They are missing a value of $x$ then.

  • If I'm right, what is the value of $x$ in $3^x = 0 \bmod 17$?

Score:6
sa flag

The group you are looking at is the multiplicative group modulo $17$ which the powers of $3$ generate. As a set, for general $n$ this does not include $0$ and is usually written as $$ (\mathbb{Z}_n^\ast,\cdot) $$ where $\mathbb{Z}_n^\ast \subseteq \{1,2,\ldots,n-1\}$ for any positive integer $n\geq 2.$

If $n=p$ is a prime then this set is actually all of $\{1,2,\ldots,p-1\}$ Otherwise, it is just the set of elements in $\mathbb{Z}_n$ that is relatively prime to $n.$ If $n=p$ a prime, then the group is also cyclic meaning a single element $g$ can generate all its members as powers $g^i\pmod p.$

For your example $p=17,$ and $g=3.$

Edit: If $n$ is nonprime, say $n=pq$ where $p\neq q$ are primes then there are $n/p$ elements in $\{0,1,\ldots, n-1\}$ that are divisible by $p.$ There are $n/q$ elements in $\{0,1,\ldots, n-1\}$ that are divisible by $q$. Since zero is divisible by both we get $$ n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right) $$ elements that are relatively prime to $n$ which is the size of the multiplicative group.

For general $n$ we have $\varphi(n)$ elements in the group, where $\varphi(\cdot)$ is Euler’s totient function.

in flag
Thank you very much! however I'm a little confused even after I searched about multiplicative groups, in this wikipedia page: https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n they state they start from 0 to n-1. I thought that the additive or multiplicative notation changed only the internal binary operation without changing any property of the group itself... so an additive cyclic group goes from 0 to n, and a multiplicative cyclic group goes from 1 to n-1? Is this correct? So sorry for my confusion, I started this topic only two days ago
in flag
Shouldn't the order of the group be equal to 17 in both cases? Is it n-1 in multiplicative cyclic groups then?
ma flag
@AndreaFarneti The article starts by saying "the integers coprime (relatively prime) to n from the set {0, 1, ..., n-1}". That means you have to filter the set and only keep the coprime integers.
ar flag
@AndreaFarneti: …and 0 is never coprime to anything. Honestly, the lead paragraph of that Wikipedia article is a bit confusingly phrased. I can see why they do it that way — it's rather natural to start with the $n$-element [ring of integers modulo $n$](https://en.wikipedia.org/wiki/Modular_arithmetic#Integers_modulo_n), drop the additive part and the elements with no multiplicative inverse, and study what remains as a multiplicative group. But if you're *not* starting that way, listing 0 as a potential element even though it can never be coprime to $n$ is kind of confusing.
in flag
@IlmariKaronen thank you very much! Now its pretty clear to me... or at least to a some degree just to know what we are talking about haha
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.