Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

On the computational complexity of determining the solvability or unsolvability of the equation $X^{2}-DY^{2}=-1$
HTML articles powered by AMS MathViewer

by J. C. Lagarias PDF
Trans. Amer. Math. Soc. 260 (1980), 485-508 Request permission

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
  • 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
    • —, Reducibility, randomness and intractability, (Proc. 9th Annual ACM Symposium on Theory of Computing), J. Assoc. Comput. Mach. (1977), 151-163.
  • N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65–72. MR 45159, DOI 10.2307/1969420
  • 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 289453, DOI 10.1515/crll.1971.248.42
  • D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. MR 93504, DOI 10.1112/S0025579300001157
  • Harvey Cohn, A second course in number theory, John Wiley & Sons, Inc., New York-London, 1962. MR 0133281
    • L. E. Dickson, Introduction to the theory of numbers, Univ. of Chicago Press, Chicago, 1929. P. G. L. Dirichlet, Werke, Vol. I, 219-236. —, De formarum binarium secundi gradus compositionae, J. Reine Angew. Math. 47 (1854), 155-160. —, Une propriété des formes quadratiques a determinant positif, J. Math. Pures Appl. (3) 1 (1856), 76-79.
  • Carl Friedrich Gauss, Disquisitiones arithmeticae, Yale University Press, New Haven, Conn.-London, 1966. Translated into English by Arthur A. Clarke, S. J. MR 0197380
  • Marshall Hall Jr., The theory of groups, The Macmillan Company, New York, N.Y., 1959. MR 0103215
  • 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
  • M. D. Hendy, The distribution of ideal class numbers of real quadratic fields, Math. Comp. 29 (1975), no. 132, 1129–1134. MR 409402, DOI 10.1090/S0025-5718-1975-0409402-4
  • L. Holzer, Minimal solutions of Diophantine equations, Canad. J. Math. 2 (1950), 238–244. MR 35783, DOI 10.4153/cjm-1950-021-0
  • Loo-keng Hua, On the least solution of Pell’s equation, Bull. Amer. Math. Soc. 48 (1942), 731–735. MR 7400, DOI 10.1090/S0002-9904-1942-07768-8
  • Pierre Kaplan, Sur le $2$-groupe des classes d’idéaux des corps quadratiques, J. Reine Angew. Math. 283(284) (1976), 313–363. MR 404206, DOI 10.1515/crll.1976.283-284.313
    • 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. D. Knuth, Seminumerical algorithms, Addison-Wesley, Reading, Mass., 1969. J. C. Lagarias, On the 4-rank of the class group of a quadratic field, J. Number Theory (to appear). —, Worst-case complexity bounds in the theory of integral quadratic forms, J. Algorithms 1 (1980). —, Succinct certificates for the solvability of binary quadratic Diophantine equations, (Proc. 20th IEEE Symposium on Foundations of Computer Science), Proc. IEEE (1979), 47-54. S. Lang, Algebraic number theory, Addison-Wesley, Reading, Mass., 1968.
  • Kenneth Manders and Leonard Adleman, $\textrm {NP}$-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
  • G. B. Mathews, Theory of numbers, Chelsea Publishing Co., New York, 1961. 2nd ed. MR 0126402
  • Patrick Morton, On Rédei’s theory of the Pell equation, J. Reine Angew. Math. 307(308) (1979), 373–398. MR 534233, DOI 10.1515/crll.1979.307-308.373
  • Władysław Narkiewicz, Elementary and analytic theory of algebraic numbers, Monografie Matematyczne, Tom 57, PWN—Polish Scientific Publishers, Warsaw, 1974. MR 0347767
  • J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 10.1017/s0305004100049252
  • Dieter Pumplün, Über die Klassenzahl und die Grundeinheit des reellquadratischen Zahlkörpers, J. Reine Angew. Math. 230 (1968), 167–210 (German). MR 224590, DOI 10.1515/crll.1968.230.167
  • 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 65588, DOI 10.1007/BF02020350
  • 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 65589, DOI 10.1007/BF02020351
    • A. Scholz, Über die Losbarkeit der Gleichung ${t^2}\, - \,D{u^2}\, = \, - \,4$, Math. Z. 39 (1934), 93-111.
  • 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
  • Daniel Shanks, Gauss’s ternary form reduction and the $2$-Sylow subgroup, Math. Comp. 25 (1971), 837–853. MR 297737, DOI 10.1090/S0025-5718-1971-0297737-4
  • Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. MR 0371855
    • H. J. S. Smith, Report on the theory of numbers, Chelsea, New York. F. Tano, Sur quelques theorems de Dirichlet, J. Reine Angew. Math. 105 (1889), 160-169.
  • 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
    • H. N. Wright, First course in theory of numbers, Wiley, New York, 1939.
  • Yoshihiko Yamamoto, Real quadratic number fields with large fundamental units, Osaka Math. J. 8 (1971), 261–270. MR 296046
  • Hideo Yokoi, Units and class numbers of real quadratic fields, Nagoya Math. J. 37 (1970), 61–65. MR 277498, DOI 10.1017/S0027763000013295
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
  • © Copyright 1980 American Mathematical Society
  • 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