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
MathSciNet review: 574794
Full-text PDF Free Access

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] Leonard Adleman and Kenneth Manders, Diophantine complexity, 17th Annual Symposium on Foundations of Computer Science (Houston, Tex., 1976) IEEE Comput. Soc., Long Beach, Calif., 1976, pp. 81–88. MR 0449009
  • [2] -, Reducibility, randomness and intractability, (Proc. 9th Annual ACM Symposium on Theory of Computing), J. Assoc. Comput. Mach. (1977), 151-163.
  • [3] N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65–72. MR 0045159
  • [4] Helmut Bauer, Zur Berechnung der 2-Klassenzahl der quadratischen Zahlkörper mit genau zwei verschiedenen Diskriminantenprimteilern, J. Reine Angew. Math. 248 (1971), 42–46 (German). MR 0289453
  • [5] D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. MR 0093504
  • [6] Harvey Cohn, A second course in number theory, John Wiley & Sons, Inc., New York-London, 1962. MR 0133281
  • [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] Carl Friedrich Gauss, Disquisitiones arithmeticae, Translated into English by Arthur A. Clarke, S. J, Yale University Press, New Haven, Conn.-London, 1966. MR 0197380
  • [12] Marshall Hall Jr., The theory of groups, The Macmillan Co., New York, N.Y., 1959. MR 0103215
  • [13] Helmut Hasse, An algorithm for determining the structure of the 2-Sylow-subgroups of the divisor class group of a quadratic number field, Symposia Mathematica, Vol. XV (Convegno di Strutture in Corpi Algebrici, INDAM, Rome, 1973) Academic Press, London, 1975, pp. 341–352. MR 0387239
  • [14] M. D. Hendy, The distribution of ideal class numbers of real quadratic fields, Math. Comp. 29 (1975), no. 132, 1129–1134. MR 0409402, 10.1090/S0025-5718-1975-0409402-4
  • [15] L. Holzer, Minimal solutions of Diophantine equations, Canadian J. Math. 2 (1950), 238–244. MR 0035783
  • [16] Loo-keng Hua, On the least solution of Pell’s equation, Bull. Amer. Math. Soc. 48 (1942), 731–735. MR 0007400, 10.1090/S0002-9904-1942-07768-8
  • [17] Pierre Kaplan, Sur le 2-groupe des classes d’idéaux des corps quadratiques, J. Reine Angew. Math. 283/284 (1976), 313–363. MR 0404206
  • [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] Kenneth Manders and Leonard Adleman, 𝑁𝑃-complete decision problems for quadratic polynomials, Eighth Annual ACM Symposium on Theory of Computing (Hershey, Pa., 1976), Assoc. Comput. Mach., New York, 1976, pp. 23–29. MR 0438804
  • [25] G. B. Mathews, Theory of numbers, 2nd ed, Chelsea Publishing Co., New York, 1961. MR 0126402
  • [26] Patrick Morton, On Rédei’s theory of the Pell equation, J. Reine Angew. Math. 307/308 (1979), 373–398. MR 534233, 10.1515/crll.1979.307-308.373
  • [27] Władysław Narkiewicz, Elementary and analytic theory of algebraic numbers, PWN—Polish Scientific Publishers, Warsaw, 1974. Monografie Matematyczne, Tom 57. MR 0347767
  • [28] J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 0354514
  • [29] Dieter Pumplün, Über die Klassenzahl und die Grundeinheit des reellquadratischen Zahlkörpers, J. Reine Angew. Math. 230 (1968), 167–210 (German). MR 0224590
  • [30] Ladislaus Rédei, Bedingtes Artinsches Symbol mit Anwendung in der Klassenkörpertheorie, Acta Math. Acad. Sci. Hungar. 4 (1953), 1–29 (German, with Russian summary). MR 0065588
  • [31] Ladislaus Rédei, Die 2-Ringklassengruppe des quadratischen Zahlkörpers und die Theorie der Pellschen Gleichung, Acta Math. Acad. Sci. Hungar. 4 (1953), 31–87 (German, with Russian summary). MR 0065589
  • [32] A. Scholz, Über die Losbarkeit der Gleichung $ {t^2}\, - \,D{u^2}\, = \, - \,4$, Math. Z. 39 (1934), 93-111.
  • [33] Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
  • [34] Daniel Shanks, Gauss’s ternary form reduction and the 2-Sylow subgroup, Math. Comp. 25 (1971), 837–853. MR 0297737, 10.1090/S0025-5718-1971-0297737-4
  • [35] Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. Congressus Numerantium, No. VII. MR 0371855
  • [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] Peter J. Weinberger, On Euclidean rings of algebraic integers, Analytic number theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972) Amer. Math. Soc., Providence, R. I., 1973, pp. 321–332. MR 0337902
  • [39] H. N. Wright, First course in theory of numbers, Wiley, New York, 1939.
  • [40] Yoshihiko Yamamoto, Real quadratic number fields with large fundamental units, Osaka J. Math. 8 (1971), 261–270. MR 0296046
  • [41] Hideo Yokoi, Units and class numbers of real quadratic fields, Nagoya Math. J. 37 (1970), 61–65. MR 0277498

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: http://dx.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