Cryptography Reference
In-Depth Information
−
positive integers such that
n
2
divides both
n
1
and
q
1. Thus the group is either
cyclic or the product of two cyclic groups and this theorem is often sufficient to
completely determine the structure of the group (up to isomorphism). Moreover, by
the structure theorem of finite abelian groups (see [45]), each finite abelian group is
isomorphic (in an essentially unique way) to a product (also called a direct sum) of
cyclic groups whose orders are prime powers (for the primes that divide the order
of the group). Quite often the group
E
will turn out to be cyclic. For example,
this is the case when the order of the group is prime (as a consequence of Lagrange's
theorem, see Corollary 2.1) and, more generally, this also happens if the order of
the group is squarefree. In this case the group is a product of cyclic groups whose
orders are pairwise relatively prime and hence it is cyclic by the Chinese remainder
theorem (Theorem 2.14). But none of these conditions are necessary for the group
to be cyclic and, indeed, there are cyclic groups of all possible orders, namely the
groups (isomorphic to)
(
F
q
)
Z
n
. In the case of elliptic curve groups we see, for example,
that the group of order 9 in Example 11.11 is cyclic and hence isomorphic to
Z
9
.
For cryptographic applications one often works with groups of prime order with
the idea of making the DLP problem in the group as hard as possible (bearing in mind
the Pohlig-Hellman algorithm). These groups have the additional advantage—not
shared by other cyclic groups—that any element
0 is a generator. However, cyclic
groups of composite order have plenty of generators too—especially in case they
have a large prime factor—because, as we have seen in Theorem 2.16, if the cyclic
group has order
n
, then the number of generators is
=
.
On some occasions we will also be interested in computing the order of a point
φ(
n
)
∈
(
F
q
)
. We know from Lagrange's theorem that the order of
P
is a divisor of the
order of the group,
P
E
(
F
q
)
|
will usually be prime or have a large prime factor and, when its factorization is known,
this leaves only a small number of divisors—just one in the prime case—as candidates
to be the order of
P
. From this we obtain a polynomial-time algorithm to compute the
order of
P
provided that multiplication of
P
by an integer—the additive analogue of
exponentiation in a multiplicative group—can also be done in polynomial time. This
is indeed the case because the binary exponentiation method works in any group and,
in particular, in any elliptic curve group where it is often called the
double-and-add
method
—the additive version of the “square-and-multiply” method we have seen
for multiplicative groups. Since, as we have mentioned, there are polynomial-time
algorithms to compute the order of the group, we see that computing the order of any
point, on input the point and the Weierstrass equation of the curve, will probably be
easy provided that factoring the group order is also easy, as is often the case.
We will also briefly mention that sometimes one goes in the opposite direction,
i.e., one tries to compute the group order starting with the known order of some
point(s). We know that the order of any point divides the group order
an
d also that,
by Hasse's theorem, the group order lies on an i
nt
erval of length 4
√
q
. Therefore,
if we find a point whose order is greater than 4
√
q
, there can be only one multiple
of this order in the Hasse interval and it must be
|
E
(
F
q
)
|
. As we will see, in cryptographic applications
|
E
. Even if the order of the
point is smaller than 4
√
q
—but not too small—we obtain only a limited number
of possibilities for
|
E
(
F
q
)
|
|
(
F
q
)
|
E
in the Hasse interval. If we know the orders of several
