What does it mean for a number to be “in the order of” a prime number?

Question

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.

Answer 1

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