Cryptography Reference
In-Depth Information
(i) Use Maple to find the prime factors of the order
o
of the group, (the value
o192
which was computed in Example 11.16) and check that it has a factor 2
4
plus
some odd prime factors.
(ii) Show that there are exactly three points of order 2 on the curve. Deduce that
the group of points cannot be cyclic because, in that case, there could only be
one element of order 2.
(iii) Find a point of order
o
2 (pick random points until one of this order is found).
(iv) Using the point computed in the previous item, find a point of order 8 on the
curve.
(v) Conclude that the group of rational points is isomorphic to
/
Z
2
×Z
o
/
2
(this is the
form provided by Cassels' theorem) and also to
Z
2
×Z
8
×Z
q
where
q
=
o
/
16
is the odd cofactor of
o
.
We briefly mention that we may use the function
EllipticPointOrder
to
give an alternative method to pseudo-randomly find a generator of a cyclic elliptic
curve group by just choosing pseudo-random points until one is found whose order
is the same as the group order. Note that, if
n
is the order of the group, the expected
number of trials is
O
(
n
/φ(
n
))
—because there are
φ(
n
)
generators—and this num-
(
(
))
ber is
O
. This algorithm is implemented by means of the following Maple
function which takes as input the curve, the group order and, optionally, the sorted
list of divisors of the order (if this list is not supplied then Maple computes it by
default).
len
n
> EllipticGroupGenerator2 := proc(E::(list(integer)), order::posint,
{orderdivisors := sort(convert(numtheory:-divisors(order), list))})
local found, P;
RandomTools:-MersenneTwister:-SetState();
found := false;
while not found do
P := PseudoRandomEllipticPoint(E);
found :=
evalb(EllipticPointOrder(P,E,order,':-orderdivisors'=orderdivisors)=order)
end do;
P
end proc:
Example 11.17
Let us use the previous function to pseudo-randomly choose a gen-
erator of the curve
ec256
in Example 11.14. We assume that the global variables
ec256
and
o256
still hold the values assigned in that example.
> EllipticGroupGenerator2(ec256, o256);
[52664204410327494153641788625224005901320065157080443069487579774976347773357,
112628236173133832734901124350015236830998302831207971620567315060380166389585]
Let us check that the order of the point thus generated is the same as the order of
the elliptic curve group:
> evalb(EllipticPointOrder(%, ec256, o256) = o256);
true
