2
$\begingroup$

Frequently, I have seen people use the term "order" in cryptography (the group-theoretic one). I have a mathematical background and "order" (say, for prime modulus $p$) is defined as the smallest integer, such that:

$$a^r \equiv 1 \pmod p$$

So, a generator (something which has the max possible order; i.e., order is $\phi(p)=p-1$) will have order $p-1$. In case of a composite group, the generator should have order $\phi(N)$.

How is it that, frequently, I read in crypto literature that people say generator has order $N$?

For example, the first answer at: When do we need composite order groups for bilinear maps and when prime order?

Am I missing some details or is my understanding incorrect?

Improve this question
$\endgroup$
2
  • $\begingroup$ For a good understanding, take a look at Lagrange theorem on finite groups, and order of an element. $\endgroup$
    – Robert NACIRI
    Jul 15, 2015 at 16:25
  • $\begingroup$ I think I see it now, thanks !! As the first answer suggests, N is not the modulus in these expressions, its the order (or size) of the group (which in general will be different from the modulus) $\endgroup$
    – CutestPenguin
    Jul 15, 2015 at 16:36

1 Answer 1

Reset to default
1
$\begingroup$

You probably know that cyclic groups of any order exist, so it is perfectly possible to have a cyclic group of order $pq$, and to consider a generator thereof.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I thought about this, so in that case the modulus will be some different number just the order will be $pq$. Is that right ? $\endgroup$
    – CutestPenguin
    Jul 15, 2015 at 16:29
  • $\begingroup$ That's probably possible, but not all groups are "integers modulo $n$", there are many other groups. The question you link deals with groups of points of elliptic curves, for example. $\endgroup$
    – fkraiem
    Jul 15, 2015 at 16:31
  • 1
    $\begingroup$ Ah, I see, thanks a lot !! As you said, even in my restricted sense of groups, $N$ they refer to is the group order and not the modulus.. This makes things a lot better, thanks !! $\endgroup$
    – CutestPenguin
    Jul 15, 2015 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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