Infrastructure (number theory)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, an infrastructure is a group-like structure appearing in global fields.

Historic development[edit]

In 1972, D. Shanks first discovered the infrastructure of a real quadratic number field and applied his baby-step giant-step algorithm to compute the regulator of such a field in \mathcal{O}(D^{1/4+\varepsilon}) binary operations (for every \varepsilon > 0), where D is the discriminant of the quadratic field; previous methods required \mathcal{O}(D^{1/2+\varepsilon}) binary operations.[1] Ten years later, H. W. Lenstra published[2] a mathematical framework describing the infrastructure of a real quadratic number field in terms of "circular groups". It was also described by R. Schoof[3] and H. C. Williams,[4] and later extended by H. C. Williams, G. W. Dueck and B. K. Schmid to certain cubic number fields of unit rank one[5][6] and by J. Buchmann and H. C. Williams to all number fields of unit rank one.[7] In his habilitation thesis, J. Buchmann presented a baby-step giant-step algorithm to compute the regulator of a number field of arbitrary unit rank.[8] The first description of infrastructures in number fields of arbitrary unit rank was given by R. Schoof using Arakelov divisors in 2008.[9]

The infrastructure was also described for other global fields, namely for algebraic function fields over finite fields. This was done first by A. Stein and H. G. Zimmer in the case of real hyperelliptic function fields.[10] It was extended to certain cubic function fields of unit rank one by R. Scheidler and A. Stein.[11][12] In 1999, S. Paulus and H.-G. Rück related the infrastructure of a real quadratic function field to the divisor class group.[13] This connection can be generalized to arbitrary function fields and, combining with R. Schoof's results, to all global fields.[14]

The one-dimensional case[edit]

An abstract definition[edit]

A one-dimensional (abstract) infrastructure (X, d) consists of a real number R > 0, a finite set X \neq \emptyset together with an injective map d : X \to \mathbb{R}/R\mathbb{Z}.[15] The map d is often called the distance map.

By interpreting \mathbb{R}/R\mathbb{Z} as a circle of circumference R and by identifying X with d(X), one can see a one-dimensional infrastructure as a circle with a finite set of points on it.

Baby steps[edit]

A baby step is an unary operation bs : X \to X on a one-dimensional infrastructure (X, d). Visualizing the infrastructure as a circle, a baby step assigns each point of d(X) the next one. Formally, one can define this by assigning to x \in X the real number f_x := \inf\{ f' > 0 \mid d(x) + f' \in d(X) \}; then, one can define bs(x) := d^{-1}(d(x) + f_x).

Giant steps and reduction maps[edit]

Observing that \mathbb{R}/R\mathbb{Z} is naturally an Abelian group, one can consider the sum d(x) + d(y) \in \mathbb{R}/R\mathbb{Z} for x, y \in X. In general, this is not an element of d(X). But instead, one can take an element of d(X) which lies nearby. To formalize this concept, assume that there is a map red : \mathbb{R}/R\mathbb{Z} \to X; then, one can define gs(x, y) := red(d(x) + d(y)) to obtain a binary operation gs : X \times X \to X, called the giant step operation. Note that this operation is in general not associative.

The main difficulty is how to choose the map red. Assuming that one wants to have the condition red \circ d = \mathrm{id}_X, a range of possibilities remain. One possible choice[15] is given as follows: for v \in \mathbb{R}/R\mathbb{Z}, define f_v := \inf\{ f \ge 0 \mid v - f \in d(X) \}; then one can define red(v) := d^{-1}(v - f_v). This choice, seeming somewhat arbitrary, appears in a natural way when one tries to obtain infrastructures from global fields.[14] Other choices are possible as well, for example choosing an element x \in d(X) such that |d(x) - v| is minimal (here, |d(x) - v| is stands for \inf\{ |f - v| \mid f \in d(x) \}, as d(x) is of the form v + R\mathbb{Z}); one possible construction in the case of real quadratic hyperelliptic function fields is given by S. D. Galbraith, M. Harrison and D. J. Mireles Morales.[16]

Relation to real quadratic fields[edit]

D. Shanks observed the infrastructure in real quadratic number fields when he was looking at cycles of reduced binary quadratic forms. Note that there is a close relation between reducing binary quadratic forms and continued fraction expansion; one step in the continued fraction expansion of a certain quadratic irrationality gives an unary operation on the set of reduced forms, which cycles through all reduced forms in one equivalence class. Arranging all these reduced forms in a cycle, Shanks noticed that one can quickly jump to reduced forms further away from the beginning of the circle by composing two such forms and reducing the result. He called this binary operation on the set of reduced forms a giant step, and the operation to go to the next reduced form in the cycle a baby step.

Relation to \mathbb{R}/R\mathbb{Z}[edit]

The set \mathbb{R}/R\mathbb{Z} has a natural group operation and the giant step operation is defined in terms of it. Hence, it makes sense to compare the arithmetic in the infrastructure to the arithmetic in \mathbb{R}/R\mathbb{Z}. It turns out that the group operation of \mathbb{R}/R\mathbb{Z} can be described using giant steps and baby steps, by representing elements of \mathbb{R}/R\mathbb{Z} by elements of X together with a relatively small real number; this has been first described by D. Hühnlein and S. Paulus[17] and by M. J. Jacobson, Jr., R. Scheidler and H. C. Williams[18] in the case of infrastructures obtained from real quadratic number fields. They used floating point numbers to represent the real numbers, and called these representations CRIAD-representations resp. (f, p)-representations. More generally, one can define a similar concept for all one-dimensional infrastructures; these are sometimes called f-representations.[15]

A set of f-representations is a subset fRep of X \times \mathbb{R}/R\mathbb{Z} such that the map \Psi_{fRep} : fRep \to \mathbb{R}/R\mathbb{Z}, \; (x, f) \mapsto d(x) + f is a bijection and that (x, 0) \in fRep for every x \in X. If red : \mathbb{R}/R\mathbb{Z} \to X is a reduction map, fRep_{red} := \{ (x, f) \in X \times \mathbb{R}/R\mathbb{Z} \mid red(d(x) + f) = x \} is a set of f-representations; conversely, if fRep is a set of f-representations, one can obtain a reduction map by setting red(f) = \pi_1(\Psi_{fRep}^{-1}(f)), where \pi_1 : X \times \mathbb{R}/R\mathbb{Z} \to X, \; (x, f) \mapsto x is the projection on $X$. Hence, sets of f-representations and reduction maps are in a one-to-one correspondence.

Using the bijection \Psi_{fRep} : fRep \to \mathbb{R}/R\mathbb{Z}, one can pull over the group operation on \mathbb{R}/R\mathbb{Z} to fRep, hence turning fRep into an abelian group (fRep, +) by x + y := \Psi_{fRep}^{-1}(\Psi_{fRep}(x) + \Psi_{fRep}(y)), x, y \in fRep. In certain cases, this group operation can be explicitly described without using \Psi_{fRep} and d.

In case one uses the reduction map red : \mathbb{R}/R\mathbb{Z} \to X, \; v \mapsto d^{-1}(v - \inf\{ f \ge 0 \mid v - f \in d(X) \}), one obtains fRep_{red} = \{ (x, f) \mid f \ge 0, \; \forall f' \in [0, f) : d(x) + f' \not\in d(X) \}. Given (x, f), (x', f') \in fRep_{red}, one can consider (x'', f'') with x'' = gs(x, x') and f'' = f + f' + (d(x) + d(x') - d(gs(x, x'))) \ge 0; this is in general no element of fRep_{red}, but one can reduce it as follows: one computes bs^{-1}(x'') and f'' - (d(x'') - d(bs^{-1}(x''))); in case the latter is not negative, one replaces (x'', f'') with (bs^{-1}(x''), f'' - (d(x'') - d(bs^{-1}(x'')))) and continues. If the value was negative, one has that (x'', f'') \in fRep_{red} and that \Psi_{fRep_{red}}(x, f) + \Psi_{fRep_{red}}(x', f') = \Psi_{fRep_{red}}(x'', f''), i.e. (x, f) + (x', f') = (x'', f'').

References[edit]

  1. ^ D. Shanks: The infrastructure of a real quadratic field and its applications. Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972), pp. 217-224. University of Colorado, Boulder, 1972. MR 389842
  2. ^ H. W. Lenstra Jr.: On the calculation of regulators and class numbers of quadratic fields. Number theory days, 1980 (Exeter, 1980), 123–150, London Math. Soc. Lecture Note Ser., 56, Cambridge University Press, Cambridge, 1982. MR 697260
  3. ^ R. J. Schoof: Quadratic fields and factorization. Computational methods in number theory, Part II, 235–286, Math. Centre Tracts, 155, Math. Centrum, Amsterdam, 1982. MR 702519
  4. ^ H. C. Williams: Continued fractions and number-theoretic computations. Number theory (Winnipeg, Man., 1983). Rocky Mountain J. Math. 15 (1985), no. 2, 621–655. MR 823273
  5. ^ H. C. Williams, G. W. Dueck, B. K. Schmid: A rapid method of evaluating the regulator and class number of a pure cubic field. Math. Comp. 41 (1983), no. 163, 235–286. MR 701638
  6. ^ G. W. Dueck, H. C. Williams: Computation of the class number and class group of a complex cubic field. Math. Comp. 45 (1985), no. 171, 223–231. MR 790655
  7. ^ J. Buchmann, H. C. Williams: On the infrastructure of the principal ideal class of an algebraic number field of unit rank one. Math. Comp. 50 (1988), no. 182, 569–579. MR 929554
  8. ^ J. Buchmann: Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper. Habilitationsschrift, Düsseldorf, 1987. PDF
  9. ^ R. Schoof: Computing Arakelov class groups. (English summary) Algorithmic number theory: lattices, number fields, curves and cryptography, 447–495, Math. Sci. Res. Inst. Publ., 44, Cambridge University Press, 2008. MR 2467554 PDF
  10. ^ A. Stein, H. G. Zimmer: An algorithm for determining the regulator and the fundamental unit of hyperelliptic congruence function field. In "Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC '91," Association for Computing Machinery, (1991), 183–184.
  11. ^ R. Scheidler, A. Stein: Unit computation in purely cubic function fields of unit rank 1. (English summary) Algorithmic number theory (Portland, OR, 1998), 592–606, Lecture Notes in Comput. Sci., 1423, Springer, Berlin, 1998. MR 1726104
  12. ^ R. Scheidler: Ideal arithmetic and infrastructure in purely cubic function fields. (English, French summary) J. Théor. Nombres Bordeaux 13 (2001), no. 2, 609–631. MR 1879675
  13. ^ S. Paulus, H.-G. Rück: Real and imaginary quadratic representations of hyperelliptic function fields. (English summary) Math. Comp. 68 (1999), no. 227, 1233–1241. MR 1627817
  14. ^ a b Fontein, F. (2011). "The Infrastructure of a Global Field of Arbitrary Unit Rank". Math. Comp. 80 (276): 2325–2357. arXiv:0809.1685. doi:10.1090/S0025-5718-2011-02490-7. 
  15. ^ a b c F. Fontein: Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures. (English summary) Adv. Math. Commun. 2 (2008), no. 3, 293–307. MR 2429459
  16. ^ S. D. Galbraith, M. Harrison, D. J. Mireles Morales: Efficient hyperelliptic arithmetic using balanced representation for divisors. (English summary) Algorithmic number theory, 342–356, Lecture Notes in Comput. Sci., 5011, Springer, Berlin, 2008. MR 2467851
  17. ^ D. Hühnlein, S. Paulus: On the implementation of cryptosystems based on real quadratic number fields (extended abstract). Selected areas in cryptography (Waterloo, ON, 2000), 288–302, Lecture Notes in Comput. Sci., 2012, Springer, 2001. MR 1895598
  18. ^ M. J. Jacobson Jr., R. Scheidler, H. C. Williams: The efficiency and security of a real quadratic field based key exchange protocol. Public-key cryptography and computational number theory (Warsaw, 2000), 89–112, de Gruyter, Berlin, 2001 MR 1881630