One-dimensional infrastructures first appeared in the 1970's in Daniel Shanks' work on real quadratic number fields ,
a squarefree integer, when he tried to fasten regulator computations. The previous algorithms used continued fraction expansion to obtain the regulator in
binary operation,
arbitrary. Shanks found out that one can obtain a multiplication like operation, which he dubbed giant steps, as opposed to the baby steps taken by one step in the continued fraction expansion. He described a baby step-giant step method to compute the regulator in
binary operations, requiring
bytes of storage. His methods were analysed, written up more clearly and extended by various people, including Hendrik Lenstra, Hugh Williams, Johannes Buchmann, Rene Schoof, and many others. Extensions of the method to function fields exist as well, most notably due to the work of Andreas Stein and Renate Scheidler.
I begin with giving an abstract definition of a one-dimensional infrastructure.
Let be a real number. A one-dimensional infrastructure of circumference
is a pair
, where
is a finite set and
is an injective map.
If you interpret as a circle of circumference
(think of it as folding up the real line, such that two numbers whose difference is an integer multiple of
are identified), a one-dimensional infrastructure can be seen as a circle with a finite number of dots on it. The map
gives the distance between
and some element
on the circle, whence
is called the distance map.
Now one can define two operations on a one-dimensional infrastructure. Due to Shanks' nomenclature, these are called baby steps and giant steps. To define a baby step, let . Then consider the set
. It is non-empty as
and bounded from below. Moreover, it is discrete as
is finite; therefore,
exists and
, say
with
. In that case, we define
. This gives a bijective map
which, in case
, has no fixed points. If
is interpreted as a circle and
identified with
,
will send each point to the “next one” in positive direction on the circle.
To define giant steps, let . For that, note that
is naturally a group, whence we can add
and
. Now
, but in general
. But we can use a similar trick as in the baby step case: we jump back to the previous point of
. For that, define
. It is bounded from above, non-empty and discrete, whence
exists with
, say
for
; then we define
. This gives a binary operation
which is in general not associative.
But even though, we have
in general, assuming that is small (here, we identify
with its smallest non-negative representant). More precisely, we have
with
, whence the giant step operation is “almost” associative.
Finite Cyclic Groups as One-dimensional Infrastructures.
Let be a finite cyclic group of order
. For
, one can write
with
; note that
is the discrete logarithm of
with respect to
. Hence, we get the isomorphism
induced by
. As
, we get the injective map
,
, turning
into a one-dimensional infrastructure.
Let ; then we get
and
, i.e. baby steps are multiplications by the generator
and the giant steps equals the group operation. In particular, this provides an example for giant steps being associative.
Therefore, one-dimensional infrastructures can be seen as generalizations of finite cyclic groups.
Remarks.
Finally, we want to sketch some ideas, which will allow generalizing infrastructures to higher dimensions. For that, let be a one-dimensional infrastructure.
First, define the map as follows. For
, define
. Again,
is non-empty, bounded from below and discrete, whence
exists and
, say
for some
. Define
. Then
satisfies
and
for all
.
If would be any other map satisfying
, one would obtain another giant step function
,
. In case
comes from a finite cyclic group, as above,
would again be the group operation. If this is not the case,
and
could be two distinct binary operations on
. If
satisfies
for all
, we would also have
This shows that our choice of is rather random; we could also define
with
, or chose
such that
, with some additional condition to rule out ties. Any other arbitrary choice of
is also possible, as long as
is satisfied. We will later see that our definition of
is exactly the one we obtain in a canonical way if we obtain infrastructures from global fields of unit rank one. We call such maps reduction maps.
Comments.