Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

On the computational complexity of determining the solvability or unsolvability of the equation $ X\sp{2}-DY\sp{2}=-1$


Author: J. C. Lagarias
Journal: Trans. Amer. Math. Soc. 260 (1980), 485-508
MSC: Primary 10B05; Secondary 68C25
DOI: https://doi.org/10.1090/S0002-9947-1980-0574794-0
MathSciNet review: 574794
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The problem of characterizing those D for which the Diophantine equation $ {X^2}\, - \,D{Y^2}\, = \, - \,1$ is solvable has been studied for two hundred years. This paper considers this problem from the viewpoint of determining the computational complexity of recognizing such D. For a given D, one can decide the solvability or unsolvability of $ {X^2}\, - \,D{Y^2}\, = \, - \,1$ using the ordinary continued fraction expansion of $ \sqrt D $, but for certain D this requires more than $ \tfrac{1}{3}\,\sqrt D \,{(\log \,D)^{ - \,1}}$ computational operations. This paper presents a new algorithm for answering this question and proves that this algorithm always runs to completion in $ O({D^{1/4\, + \,\varepsilon }})$ bit operations. If the input to this algorithm includes a complete prime factorization of D and a quadratic nonresidue $ {n_i}$ for each prime $ {p_i}$ dividing D, then this algorithm is guaranteed to run to completion in $ O({(\log \,D)^5}\,(\log \,\log \,D)(\log \,\log \,\log \,D))$ bit operations. This algorithm is based on an algorithm that finds a basis of forms for the 2-Sylow subgroup of the class group of binary quadratic forms of determinant D.


References [Enhancements On Off] (What's this?)

  • [1] L. Adleman and K. Manders, Diophantine complexity, (Proc. 17th IEEE Symposium on Foundations of Computer Science), Proc. IEEE (1976), 81-88. MR 0449009 (56:7314)
  • [2] -, Reducibility, randomness and intractability, (Proc. 9th Annual ACM Symposium on Theory of Computing), J. Assoc. Comput. Mach. (1977), 151-163.
  • [3] N. Ankeny, The least quadratic nonresidue, Ann. of Math. (2) 55 (1952), 65-72. MR 0045159 (13:538c)
  • [4] H. Bauer, Zur Berechnung der 2-Klassenzahl der quadratischer Zahlkorper mit genau zwei verscheidenen Discriminantenprimzahlen, J. Reine Angew. Math. 248 (1971), 42-46. MR 0289453 (44:6643)
  • [5] D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106-112. MR 0093504 (20:28)
  • [6] H. Cohn, A second course in number theory, Wiley, New York, 1962. MR 0133281 (24:A3115)
  • [7] L. E. Dickson, Introduction to the theory of numbers, Univ. of Chicago Press, Chicago, 1929.
  • [8] P. G. L. Dirichlet, Werke, Vol. I, 219-236.
  • [9] -, De formarum binarium secundi gradus compositionae, J. Reine Angew. Math. 47 (1854), 155-160.
  • [10] -, Une propriété des formes quadratiques a determinant positif, J. Math. Pures Appl. (3) 1 (1856), 76-79.
  • [11] C. F. Gauss, Disquisitiones arithmeticae, 1801; English translation, Yale Univ. Press, New Haven, Conn., 1966. MR 0197380 (33:5545)
  • [12] M. Hall, Jr., The theory of groups, Macmillan, New York, 1959. MR 0103215 (21:1996)
  • [13] H. Hasse, An algorithm for determining the structure of the 2-Sylow-subgroup of the divisor class group of a quadratic number field, Symposia Mathematica 15 (1975), 341-352. MR 0387239 (52:8082)
  • [14] M. D. Hendy, The distribution of ideal class numbers of quadratic fields, Math. Comp. 29 1975), 1129-1134. MR 0409402 (53:13157)
  • [15] L. Holzer, Minimal solutions of Diophantine equations, Canad. J. Math. 2 (1950), 238-244. MR 0035783 (12:11b)
  • [16] L. K. Hua, On the least solution to Pell's equation, Bull. Amer. Math. Soc. 48 (1942), 731-735. MR 0007400 (4:130f)
  • [17] P. Kaplan, Sur le 2-groupe des classes d'ideaux des corps quadratiques, J. Reine Angew. Math. 283/284 (1976), 313-363. MR 0404206 (53:8009)
  • [18] P. Kaplan and C. Sanchez, Table des 2-groupe des classes d'ideaux de $ Q(\sqrt {2p} )$ pour $ p\, < \,2\, \cdot \,{10^6}$, U.E.R. de Mathematique, Université de Nancy I, Nancy, France, 1974.
  • [19] D. Knuth, Seminumerical algorithms, Addison-Wesley, Reading, Mass., 1969.
  • [20] J. C. Lagarias, On the 4-rank of the class group of a quadratic field, J. Number Theory (to appear).
  • [21] -, Worst-case complexity bounds in the theory of integral quadratic forms, J. Algorithms 1 (1980).
  • [22] -, Succinct certificates for the solvability of binary quadratic Diophantine equations, (Proc. 20th IEEE Symposium on Foundations of Computer Science), Proc. IEEE (1979), 47-54.
  • [23] S. Lang, Algebraic number theory, Addison-Wesley, Reading, Mass., 1968.
  • [24] K. Manders and L. Adleman, NP-complete decision problems for quadratic polynomials, (Proc. 8th ACM Conference on Theory of Computing), J. Assoc. Comput. Mach. (1976), 23-29. MR 0438804 (55:11710)
  • [25] G. B. Mathews, Theory of numbers, 2nd ed., Chelsea, New York, (Reprint 1961). MR 0126402 (23:A3698)
  • [26] P. Morton, On Redei's theory of the Pell equation, J. Reine Angew Math. 307/8 (1979), 373-398. MR 534233 (81f:12005)
  • [27] W. Narkiewicz, Elementary and analytic theory of algebraic numbers, PWN, Warsaw, 1974. MR 0347767 (50:268)
  • [28] J. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521-528. MR 0354514 (50:6992)
  • [29] D. Pumplün, Über die Klassenzahl und die Grundeinheit des reelquadratischen Zahlkorper, J. Reine Angew. Math. 230 (1968), 167-210. MR 0224590 (37:189)
  • [30] L. Redei, Bedingtes Artinsches symbol mit Andwendung in der Klassenkörpertheorie, Acta Math. Acad. Sci. Hungar. 4 (1953), 1-29. MR 0065588 (16:450d)
  • [31] -, Die 2-Ringklassengruppe des Quadratischen Zahlkörpers und die theorie der Pellschen Gleichung, Acta Math. Acad. Sci. Hungar. 4 (1953), 31-87. MR 0065589 (16:450e)
  • [32] A. Scholz, Über die Losbarkeit der Gleichung $ {t^2}\, - \,D{u^2}\, = \, - \,4$, Math. Z. 39 (1934), 93-111.
  • [33] D. Shanks, Class number, a theory of factorization, and genera, (1969 Number Theory Institute), Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, R. I., 1971, pp. 415-440. MR 0316385 (47:4932)
  • [34] -, Gauss's ternary form reduction and the 2-Sylow subgroup, Math. Comput. 25 (1971), 837-853. MR 0297737 (45:6789)
  • [35] -, Five number-theoretic algorithms, (Proc. 2nd Manitoba Conf. on Numerical Mathematics), 1972, 51-70. MR 0371855 (51:8072)
  • [36] H. J. S. Smith, Report on the theory of numbers, Chelsea, New York.
  • [37] F. Tano, Sur quelques theorems de Dirichlet, J. Reine Angew. Math. 105 (1889), 160-169.
  • [38] P. J. Weinberger, Euclidean rings of algebraic integers, Analytic Number Theory, Proc. Sympos. Pure Math., vol. 24, Amer. Math. Soc., Providence, R. I., 1973, pp. 321-332. MR 0337902 (49:2671)
  • [39] H. N. Wright, First course in theory of numbers, Wiley, New York, 1939.
  • [40] Y. Yamamoto, Real quadratic fields with large fundamental units, Osaka J. Math. 8 (1971), 261-270. MR 0296046 (45:5107)
  • [41] H. Yokoi, Units and class numbers of real quadratic fields, Nagoya Math. J. 37 (1970), 61-65. MR 0277498 (43:3231)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 10B05, 68C25

Retrieve articles in all journals with MSC: 10B05, 68C25


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1980-0574794-0
Keywords: Computational complexity, binary quadratic forms, form class group, composition of forms, Pell's equation, Diophantine equation
Article copyright: © Copyright 1980 American Mathematical Society

American Mathematical Society