1
$\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 an 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$
  • $\begingroup$ For a good understanding, take a look at Lagrange theorem on finite groups, and order of an element. $\endgroup$ – Robert NACIRI Jul 15 '15 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 '15 at 16:36
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$
  • $\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 '15 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 '15 at 16:31
  • $\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 '15 at 16:38

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.