Let be a one-dimensional infrastructure of circumference
. We have seen that we obtain two operations
and
together with a reduction map
, and we have
for
. This gives us a binary operation which is in general not associative. For several reasons, it would be interesting to embed the infrastructure into a group. An obvious choice for such a group would be
, as we can identify
as a subset of
by identifying it with
. Such an interpretation of the infrastructure as part of a “circular group” has first been considered by Hendrik Lenstra in his 1980 paper On the computation of regulators and class numbers of quadratic fields.
The idea is to consider pairs ; the map
,
is obviously surjective, but far from being injective. Hence, it would be a good idea to restrict
to a subset which makes this map both injective and surjective. We want this subset to contain
; note that
is injective and essentially equals
by the identification
,
. We obtain the following definition:
A set of -representations of
is a set
such that
is bijective and such that
.
But how to obtain such a subset? In fact, we already have all ingredients ready, as the following proposition shows, by relating -representations to reduction maps:
Let be a one-dimensional infrastructure. Let
be the set of reduction maps and
be the set of
-representations for
. The map
is a bijection, with its inverse given by
where ,
is the projection onto the first component.
Now fix one corresponding choice of and
, and let
,
be the associated bijection. Then
for all with
being the projection. Moreover, using the bijection
,
becomes a group which we will write additively by
, which extends the giant steps.
Finally, let be the map we originally defined for infrastructures, i.e.
for
. In that case, one can compute the group operation on
without having to evalute
or
, with only computing baby and giant steps and relative distances, i.e.
resp.
for
:
Let and
, and let
. Then
can be computed with one giant step computation and at most
baby step computations as follows:
- Compute
and
.
- Compute
and
.
- If
, set
and go to step 2.
- Return the pair
.
In the case of infrastructures obtained from global fields, we are also able to describe the group operation in without having to evaluate
or
. In fact, evaluating
or
is essentially the discrete logarithm problem, for which so far no general polynomial methods for solving it exist in the case of global fields.
Comments.