Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A deterministic algorithm for solving $ n=fu\sp 2+gv\sp 2$ in coprime integers $ u$ and $ v$


Authors: Kenneth Hardy, Joseph B. Muskat and Kenneth S. Williams
Journal: Math. Comp. 55 (1990), 327-343
MSC: Primary 11Y50; Secondary 11D09
DOI: https://doi.org/10.1090/S0025-5718-1990-1023762-3
MathSciNet review: 1023762
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We give a deterministic algorithm for finding all primitive representations of a natural number n in the form $ f{u^2} + g{v^2}$, where f and g are given positive coprime integers, and $ n \geq f + g + 1$, $ (n,fg) = 1$. The running time of this algorithm is at most

$\displaystyle \mathcal{O}({n^{1/4}}{(\log n)^3}(\log \log n)(\log \log \log n)),$

uniformly in f and g.

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

  • [1] L. M. Adleman, C Pomerance, and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), 173-206. MR 683806 (84e:10008)
  • [2] W. S. Anglin, $ {x^2} \equiv R$ $ \pmod p$, Preprint, McGill University, 1987.
  • [3] J. Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972). 1011-1013. MR 0314745 (47:3297)
  • [4] D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1975), 106-112. MR 0093504 (20:28)
  • [5] M. Cipolla, Un metodo per la risoluzione della congruenza di secondo grado, Rend. Accad. Sci. Fis. Mat. Napoli (3) 9 (1903), 154-163.
  • [6] G. Cornacchia, Su di un metodo per la risoluzione in numeri interi dell'equazione $ \sum\nolimits_{h = 0}^n {{c_h}{x^{n - h}}{y^h} = P} $. Giornale di Matematiche di Battaglini 46 (1908), 33-90.
  • [7] L. E. Dickson, History of the theory of numbers, vol. I, Chelsea, New York, 1952.
  • [8] C. Hermite, Note au sujet de l'article précédent, J. Math. Pures Appl. 13 (1848), 15.
  • [9] D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory (W. J. LeVeque, ed.), MAA Studies in Math., vol. 6, Math. Assoc. America, Washington, D. C.,, 1969, pp. 117-151. MR 0246815 (40:84)
  • [10] C. Pomerance, Lecture notes on primality testing and factoring, MAA Notes No. 4 (1984).
  • [11] -, Fast, rigorous factorization and discrete logarithm algorithms, Discrete Algorithms and Complexity (D. S. Johnson, T. Nishizeki, A. Nozaki, and H. S. Wilf, eds.), Academic Press, 1987, pp. 119-143. MR 910929 (88m:11109)
  • [12] -, Analysis and comparison of some integer factoring algorithms, Computational Methods in Number Theory (Part I) (H. W. Lenstra and R. Tijdeman, eds.), Math. Centre Tracts, vol. 154, Mathematisch Centrum, Amsterdam, 1982, pp. 89-139. MR 700260 (84i:10005)
  • [13] H. Riesel, Prime numbers and computer methods for factorization, Birkhäuser, Basel and New York, 1985. MR 897531 (88k:11002)
  • [14] R. Schoof, Elliptic curves over finite fields and the computation of square roots $ \bmod p$. Math. Comp. 44 (1985), 483-494. MR 777280 (86e:11122)
  • [15] J. A. Serret, Sur un théorème rélatif aux nombres entières, J. Math. Pures Appl. 13 (1848), 12-14.
  • [16] D. Shanks, Five number-theoretic algorithms, Proc. Second Manitoba Conference on Numerical Mathematics, University of Manitoba, Winnipeg, Canada, 1972, pp. 51-70. MR 0371855 (51:8072)
  • [17] A. Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen, Gött. Nachr. (1891), 344-346.
  • [18] J. V. Uspensky and M. A. Heaslet, Elementary number theory, McGraw-Hill, New York, 1939.
  • [19] P. Wilker, An efficient algorithmic solution of the Diophantine equation $ {u^2} + 5{v^2} = m$, Math. Comp. 35 (1980), 1347-1352. MR 583512 (81m:10021)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y50, 11D09

Retrieve articles in all journals with MSC: 11Y50, 11D09


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1990-1023762-3
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society