Skip to main content.

One-dimensional Infrastructures.

.

One-dimensional infrastructures first appeared in the 1970's in Daniel Shanks' work on real quadratic number fields \Q(\sqrt{D}), D > 1 a squarefree integer, when he tried to fasten regulator computations. The previous algorithms used continued fraction expansion to obtain the regulator in \calO(D^{1/2 + \varepsilon}) binary operation, \varepsilon > 0 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 \calO(D^{1/4 + \varepsilon}) binary operations, requiring \calO(D^{1/4 + \varepsilon}) 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.

Definition (One-dimensional infrastructure).

Let R > 0 be a real number. A one-dimensional infrastructure of circumference R is a pair (X, d), where X \neq \emptyset is a finite set and d : X \to \R/R\Z is an injective map.

If you interpret \R/R\Z as a circle of circumference R (think of it as folding up the real line, such that two numbers whose difference is an integer multiple of R are identified), a one-dimensional infrastructure can be seen as a circle with a finite number of dots on it. The map d gives the distance between 0 \in \R/R\Z and some element x \in X on the circle, whence d 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 x \in X. Then consider the set F_x := \{ f \in \R \mid f > 0, \; d(x) + f \in d(X) \}. It is non-empty as R \in F_x and bounded from below. Moreover, it is discrete as X is finite; therefore, f := \min F_x exists and d(x) + f \in d(X), say d(x) + f = d(x') with x' \in X. In that case, we define \bs(x) := x'. This gives a bijective map \bs : X \to X which, in case \abs{X} > 1, has no fixed points. If \R/R\Z is interpreted as a circle and X identified with d(X), \bs will send each point to the “next one” in positive direction on the circle.

To define giant steps, let x, x' \in X. For that, note that \R/R\Z is naturally a group, whence we can add d(x) and d(x'). Now d(x) + d(x') \in \R/R\Z, but in general d(x) + d(x') \not\in d(X). But we can use a similar trick as in the baby step case: we jump back to the previous point of d(X). For that, define F_{x,x'} := \{ f \in \R \mid f \ge 0, \; d(x) + d(x') - f \in d(X) \}. It is bounded from above, non-empty and discrete, whence f := \max F_{x,x'} exists with d(x) + d(x') - f' \in d(X), say d(x) + d(x') - f = d(y) for y \in X; then we define \gs(x, x') := y. This gives a binary operation \gs : X \times X \to X which is in general not associative.

But even though, we have

d(\gs(x, x')) \approx d(x) + d(x')

in general, assuming that D := \max\{ d(\bs(x)) - d(x) \mid x \in X \} is small (here, we identify d(\bs(x)) - d(x) \in \R/R\Z with its smallest non-negative representant). More precisely, we have d(\gs(x, x')) + f = d(x) + d(x') with 0 \le f < D, whence the giant step operation is “almost” associative.

Finite Cyclic Groups as One-dimensional Infrastructures.

Let G = \ggen{g} be a finite cyclic group of order R. For h \in G, one can write h = g^n with n \in \Z; note that n = \log_g h \in \Z/R\Z is the discrete logarithm of h with respect to g. Hence, we get the isomorphism G \cong \Z/R\Z induced by \log_g : G \to \Z/R\Z. As \Z/R\Z \subseteq \R/R\Z, we get the injective map d : G \to \R/R\Z, h \mapsto \log_g h, turning (G, d) into a one-dimensional infrastructure.

Let h, h' \in G; then we get \bs(h) = g h and \gs(h, h') = h h', i.e. baby steps are multiplications by the generator g 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 (X, d) be a one-dimensional infrastructure.

First, define the map red : \R/R\Z \to X as follows. For r \in \R/R\Z, define F_r := \{ f \in \R \mid f \ge 0, \; r - f \in d(X) \}. Again, F_r is non-empty, bounded from below and discrete, whence f := \min F_r exists and r - f \in d(X), say r - f = d(x) for some x \in X. Define red(r) := x. Then red satisfies red \circ d = \id_X and \gs(x, x') = red(d(x) + d(x')) for all x, x' \in X.

If red' : \R/R\Z \to X would be any other map satisfying red' \circ d = \id_X, one would obtain another giant step function \gs' : X \times X \to X, (x, x') \mapsto red'(d(x) + d(x')). In case X comes from a finite cyclic group, as above, \gs' would again be the group operation. If this is not the case, \gs and \gs' could be two distinct binary operations on X. If red' satisfies d(red'(r)) \approx r for all r \in \R/R\Z, we would also have

d(\gs'(x, x')) \approx d(x) + d(x') \text{ for all } x, x' \in X.

This shows that our choice of red is rather random; we could also define red(r) = d^{-1}(d(x) + f) with f = \min \{ f \in \R \mid f \ge 0, \; r + f \in d(X) \}, or chose f such that \abs{f} = \min\{ \abs{f} \mid r + f \in d(X) \}, with some additional condition to rule out ties. Any other arbitrary choice of red is also possible, as long as red \circ d = \id_X is satisfied. We will later see that our definition of red 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.

Categories: Algebra Number Theory
Tags:

Comments.

No comments.