2
$\begingroup$

I'm doing a few exercises regarding Schnorr's identification scheme. I have the exercise starting off like this, with the values defined:

Let $p = 311$ and $r = 31\ |\ (p - 1)$. Let $g = 169$, which has order $r$.

I just really can't figure out what the vertical bar means here?

Sometimes in discrete maths, a vertical bar means absolute value, sometimes two them are cardinalty? Programming would suggest that it means a logical or?

One place I saw something indicating that it might be xor, but I really have no idea.

$\endgroup$
2
  • 1
    $\begingroup$ Do you have more context? $|$ can also mean divides in that 31 divides 310, but it doesn't make sense to assign that to $r$ $\endgroup$ May 18 at 15:57
  • $\begingroup$ @AmanGrewal This is apparently a widely used problem, see books.google.com/… for one example. $\endgroup$ May 18 at 16:52
5
$\begingroup$

The meaning of that $\ \vert\ $ in this context is divides (as in evenly divides, or is a divisor of), and that's a standard usage of this sign. The quote should be read as:

let $p=311$ and $r=31$, which divides $(p-1)$. Let $g=169$

In other words: $r$ is a divisor of $p-1$. Or, exists integer $q$ with $r\times q=p-1$. Or, $((p-1)\bmod r)=0$, also writable as $p-1\bmod r=0$ or $p-1\equiv0\pmod r$ or $p\equiv1\pmod r$. In many common programing languages, (p-1)%r == 0. That's because $31$ (evenly) divides $311-1$, since $31\times10=310$.

That was correctly guessed by Aman Grewal in comment, but as noted, proximity with the assignment makes the notation confusing. Elision of the implied which is something I would try to avoid.


The end of the sentence says «Let $g=169$, which has order $r$». Does that mean that $g$ is really 169%31?

No. The term order is used in its meaning in group theory. In this context, it means that when we repeatedly multiply $1$ by $g$, reducing modulo $p$ after each multiplication, we'll first get back to $1$ after performing $r$ multiplications. That's related to $r\,\vert\,(p-1)$, because the order of any element in a finite group is a divisor of the order of the group, that is the number of elements in the group. Here the group is the multiplicative group modulo $p$, noted $\mathbb Z_p^*$ or $(\mathbb Z/p\mathbb Z)^\times$, which has $p-1$ elements since $p$ is prime. The powers of $g$ form a subgroup of order $r$, called a Schnorr group.

$\endgroup$
4
  • $\begingroup$ Thanks, One more thing that I don't understand. The end of the sentence says Let G=169, which has order r does that mean that G is really 169%31? $\endgroup$
    – Garsty100
    May 18 at 17:37
  • $\begingroup$ thanks a lot again. A quick addition though,. I have just received an answe that the actual value of r is actually 8? How does this make sense? $\endgroup$
    – Garsty100
    May 18 at 18:04
  • 1
    $\begingroup$ @Garsty100: Asking Wolfram order of 169 modulo 311 yields 31, thus the quote is correct. I recommend studying some group theory. That serves in many fields (including the non-mathematical sense of that). $\endgroup$
    – fgrieu
    May 18 at 18:42
  • 1
    $\begingroup$ “Let… $r$ be 31, which divides $(p-1)$…” $\endgroup$ May 19 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.