In some papers I'm looking at there is some language that says things like "Choose a random number in the order of prime q" and I see some syntax that it is referring to that looks s = Zq (where q is a subscript). What does it mean for a number to be "in the order of" some prime?

For context, the paper I am reading is The Twin Diffie-Hellman Problem and Applications.

Here is a link to the paper: https://eprint.iacr.org/2008/067.pdf


You are (slightly) misreading the statements. I've checked through all 13 occurrences of the word "order" in that paper, and see only "typical" statements, such as:

Let $\mathbb{G}$ be a group of prime order $q$

"Order" means one of two things in group theory:

  1. The order of a group is just the number of elements in it. So a group of prime order $q$ is just a group $\mathbb{G}$ where $|\mathbb{G}| = q$.
  2. The order of an element of a group $g\in\mathbb{G}$ is how many times you have to repeat the group operation of $g$ to get to the identity. For a group written additively, it's the smallest $n$ such that $ng = 0$. For a group written multiplicatively, its the smallest $n$ such that $g^n = 1$.

These are (sort of) connected by a result in group theory that says that $\forall g\in\mathbb{G}, g^{|\mathbb{G}|} = 1$. As a consequence, the order of an element always divides the order of the group. This is a generalization of both Fermat's little theorem and Euler's theorem.

The paper you're reading only seems to use order to mean the first of these two things. Note that groups of prime order are special in that they're always cyclic groups. The most basic example of a cyclic group is $\mathbb{Z}/p\mathbb{Z}$, and in fact every cyclic group is isomorphic to a group of this form. Note that this isomorphism is generally not efficiently computable, which is good because the discrete logarithm problem is easy in $\mathbb{Z}/p\mathbb{Z}$.

| improve this answer | |
  • 1
    $\begingroup$ These are connected by the fact that the order of an element is the order of the subgroup it generates. $\endgroup$ – fkraiem Dec 10 '19 at 9:35
  • $\begingroup$ @kansas_bulldog382: "Choose a random number in the order of prime $q$" has no precise meaning, but includes choosing an integer uniformly at random in $[0,q)$, or in $[0,2^{\lfloor\log_2(q)\rfloor})$ (the later eases generating it from a random bit generator). As stated in the answer, that turn of phrase is not used in the linked paper. $\endgroup$ – fgrieu Dec 11 '19 at 10:28

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.