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.