Some methods for evaluating the regulator of a real quadratic function field. (English) Zbl 0987.11071

The analogy between algebraic number fields and algebraic function fields is a well-known fact. However, many assertions conjectured for number fields can be proved for function fields. The most spectacular example in this respect is the Riemann hypothesis.
The present paper can therefore, in a way, be regarded as the detection of function fields for cryptographic applications. It is devoted to the efficient computation of the regulator \(R\) of a quadratic (hyperelliptic) function field \(F/K\), \(K = \mathbb F_q\). The regulator \(R\) is not only an important invariant of \(F/K\), it is also of cryptographic relevance. To support the first point of view, we mention only the relation \[ h = R h', \] where \(h\) is the divisor class number and \(h'\) is the ideal class number of \(F/K\). For the second point of view, we point out that a key-exchange protocol can be designed on the basis of the arithmetic of quadratic function fields \(F/K\).
Shank’s method of baby-steps and giant-steps has found many applications. It was well-developed for number fields by Williams and Wunderlich resp. by Williams and Stephens. The analogy with function fields requires some extra considerations carried out in the paper under consideration.
The paper is based on the diploma thesis of the first author written under the reviewer as an advisor. The theory of quadratic congruence function fields was developed by Artin in his dissertation.
For the computation of \(R\), two efficient continued-fraction algorithms (3.8 and 4.4) are presented here, one (3.8) in time \(O(q^{1/4})\), which came up already in the diploma thesis of Stein, and the other (4.4) relying on ideas of Lenstra and Schoof for number fields in time \(O(q^{1/5})\). The adaptation of the methods of Lenstra and Schoof to function fields, resulting in the second algorithm (4.4) in time \(O(q^{1/5})\), is the essential contribution of Hugh Williams. The analogy of the Riemann hypothesis is used to calculate the complexities. Here, \(K = \mathbb F_q\) is the finite field with \(q\) elements, and in the algorithms, \(q = p\) is a prime number.
The computational complexity is a theoretical entity. An algorithm with a better complexity might not perform so well in reality. Everything depends on the constants involved. The authors state nonetheless that algorithm 3.8 works efficiently for regulators \(R \leq 10^6\) and algorithm 4.4 for regulators \(R \geq 10^8\). This statement is corroborated by the examples in table 2.


11R58 Arithmetic theory of algebraic function fields
11Y40 Algebraic number theory computations
11Y65 Continued fraction calculations (number-theoretic aspects)
12E30 Field arithmetic
Full Text: DOI Euclid EuDML


[1] Artin E., Mathematische Zeitschrift 19 pp 153– (1924) · JFM 50.0107.01
[2] Artin E., Mathematische Zeitschrift 19 pp 208– (1924)
[3] Buchmann J., Math. Comp. 53 (188) pp 679– (1989)
[4] Deuring M., Lectures on the theory of algebraic functions of one variable (1973) · Zbl 0249.14008
[5] Eichler M., Introduction to the theory of algebraic numbers and functions (1966) · Zbl 0152.19502
[6] Lenstra H. W., Journées arithmetiques pp 123– (1982)
[7] Neild C., Math. Comp. 28 pp 279– (1974)
[8] Perron O., Die Lehre von den Kettenbrüchen (1913) · JFM 43.0283.04
[9] Reichardt H., Mathematische Zeitschrift 40 pp 713– (1936) · Zbl 0013.10302
[10] Scheidler R., Design Codes Cryptogr. 7 pp 1– (1996)
[11] Schmidt F. K., Mathematische Zeitschrift 33 pp 1– (1931) · Zbl 0001.05401
[12] Schoof R. J., Computational methods in number theory II pp 235– (1982)
[13] Shanks, D. 1971.”Class number, a theory of factorization and genera”415–440. Providence: Amer. Math. Soc. [Shanks 1971], in 1969Number Theory Institute(Stony Brook), Proc. Symp. Pure Math. 20 · Zbl 0223.12006
[14] Shanks, D. ”The infrastructure of a real quadratic field and its applications”. Proceedings of the Number Theory Conference. 1972, Boulder. pp.217–224. Boulder, CO: Univ. Colorado. [Shanks 1972] · Zbl 0334.12005
[15] Stein, A. 1992.Baby Step-Giant Step-Verfahren in reell-quadratischen Kongruenzfunktionenkörpern mit Charakteristik ungleich2Saarbrücken: Diplomarbeit, Univ. des Saarlandes, [Stein 1992]
[16] Stein A., ISSAC ’91 (Bonn, 1991) pp 183– (1991)
[17] Stephens A. J., Math. Comp. 50 (182) pp 619– (1988)
[18] Stephens A. J., Math. Comp. 51 (184) pp 809– (1988)
[19] Weis B., Mitt. Math. Ges. Hamburg 12 (2) pp 261– (1991)
[20] Williams H. C., Math. Comp. 48 (177) pp 405– (1987)
[21] Zimmer H. G., ”SIMATH Manual”
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.