Interpreting One-dimensional Infrastructures as Groups: f-Representations.

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:

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:

Theorem.

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 :

Theorem.

Let and , and let . Then can be computed with one giant step computation and at most baby step computations as follows:

1. Compute and .
2. Compute and .
3. If , set and go to step 2.
4. 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.