A Note on NUCOMP

van der Poorten, Alfred

doi:10.1090/S0025-5718-03-01518-7

A Note on NUCOMP
HTML articles powered by AMS MathViewer

by Alfred J. van der Poorten PDF

Math. Comp. 72 (2003), 1935-1946 Request permission

Abstract:

This note is a detailed explanation of Shanks–Atkin NUCOMP—composition and reduction carried out “simultaneously”—for all quadratic fields, that is, including real quadratic fields. That explanation incidentally deals with various “exercises” left for confirmation by the reader in standard texts. Extensive testing in both the numerical and function field cases by Michael J Jacobson, Jr, reported elsewhere, confirms that NUCOMP as here described is in fact efficient for composition both of indefinite and of definite forms once the parameters are large enough to compensate for NUCOMP’s extra overhead. In the numerical indefinite case that efficiency is a near doubling in speed already exhibited for discriminants as small as $10^7$.

References

A. O. L. Atkin, Letter to Dan Shanks on the programs NUDUPL and NUCOMP, 12 December 1988; from the Nachlaß of D. Shanks and made available to me by Hugh C. Williams.
Duncan A. Buell, Binary quadratic forms, Springer-Verlag, New York, 1989. Classical theory and modern computations. MR 1012948, DOI 10.1007/978-1-4612-4542-1
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Felix Klein, Elementary mathematics from an advanced standpoint: Geometry, reprint (New York: Dover, 1939); see §IIff.
Hermann Grassmann, A new branch of mathematics, Open Court Publishing Co., Chicago, IL, 1995. The Ausdehnungslehre of 1844 and other works; Translated from the German and with a note by Lloyd C. Kannenberg; With a foreword by Albert C. Lewis. MR 1637704
W. V. D. Hodge and D. Pedoe, Methods of algebraic geometry. Vol. I, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1994. Book I: Algebraic preliminaries; Book II: Projective space; Reprint of the 1947 original. MR 1288305, DOI 10.1017/CBO9780511623899
Michael J Jacobson Jr and Alfred J van der Poorten, “Computational aspects of NUCOMP”, to appear in Claus Fieker and David Kohel eds, Algorithmic Number Theory (Proc. Fifth International Symposium, ANTS-V, Sydney, NSW, Australia July 2002), Springer Lecture Notes in Computer Science 2369 (2002), 120–133.
H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR 697260
T. Radó and P. Reichelderfer, On a stretching process for surfaces, Amer. J. Math. 61 (1939), 645–650. MR 47, DOI 10.2307/2371318
Daniel Shanks, On Gauss and composition. I, II, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 163–178, 179–204. MR 1123074