|
A Note on NUCOMP
Author(s):
Alfred
J.
van der Poorten.
Journal:
Math. Comp.
72
(2003),
1935-1946.
MSC (2000):
Primary 11Y40, 11E16, 11R11
Posted:
April 29, 2003
MathSciNet review:
1986813
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
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  .
References:
-
- 1.
- 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.
- 2.
- Duncan A. Buell, ``Binary quadratic forms. Classical theory and modern computations'', Springer-Verlag, New York, 1989, x+247pp. MR 92b:11021
- 3.
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, 138, Springer-Verlag, Berlin, 1993, xii+534pp. MR 94i:11105
- 4.
- Felix Klein, Elementary mathematics from an advanced standpoint: Geometry, reprint (New York: Dover, 1939); see §IIff.
- 5.
- Hermann Grassmann, A New Branch of Mathematics, Open Court: Chicago and La Salle, Illinois: 1995. MR 99e:01015
- 6.
- W. V. D. Hodge and D. Pedoe, Methods of Algebraic Geometry (Cambridge: Cambridge University Press, 1953); see Vol.1, Chapter VII. MR 95d:14002a
- 7.
- 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.
- 8.
- H. W. Lenstra Jr., ``On the calculation of regulators and class numbers of quadratic fields'', in J. V. Armitage ed., ``Journées Arithmétiques 1980'' LMS Lecture Notes 56, Cambridge 1982, 123-151. MR 86g:11080
- 9.
- D. Shanks, ``Class number, a theory of factorization, and genera'', in Proc. Symp. Pure Math. 20 (1969 Institute on Number Theory), Amer. Math. Soc., Providence 1971, 415-440; see also ``The infrastructure of a real quadratic field and its applications'', Proc. Number Theory Conference, Univ. of Colorado, Boulder, CO, 1972, 217-224. MR 47:4932; MR 52:10762
- 10.
- Daniel Shanks, ``On Gauss and composition'', in Number Theory and Applications, ed. Richard A. Mollin, (NATO-Advanced Study Institute, Banff, 1988) (Kluwer Academic Publishers Dordrecht, 1989), 163-204. MR 92e:11150
Similar Articles:
Retrieve articles in Mathematics of Computation
with
MSC (2000):
11Y40, 11E16, 11R11
Retrieve articles in all Journals with
MSC (2000):
11Y40, 11E16, 11R11
Additional Information:
Alfred
J.
van der Poorten
Affiliation:
ceNTRe for Number Theory Research, 1 Bimbil Pl. Killara, New South Wales 2071, Australia
Email:
alf@math.mq.edu.au
DOI:
10.1090/S0025-5718-03-01518-7
PII:
S 0025-5718(03)01518-7
Keywords:
Binary quadratic form,
composition
Received by editor(s):
January 10, 2002
Posted:
April 29, 2003
Additional Notes:
The author was supported in part by a grant from the Australian Research Council
Copyright of article:
Copyright
2003,
American Mathematical Society
|
