A deterministic algorithm for solving 𝑛=𝑓𝑢²+𝑔𝑣² in coprime integers 𝑢 and 𝑣

Hardy, Kenneth; Muskat, Joseph B.; Williams, Kenneth S.

doi:10.1090/S0025-5718-1990-1023762-3

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

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$ , . 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.

[1] Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, https://doi.org/10.2307/2006975
[2] W. S. Anglin, ${x^2} \equiv R$ $\pmod p$ , Preprint, McGill University, 1987.
[3] John Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), 1011–1013. MR 314745, https://doi.org/10.1090/S0025-5718-1972-0314745-6
[4] D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. MR 93504, https://doi.org/10.1112/S0025579300001157
[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, Math. Assoc. Amer. (distributed by Prentice-Hall, Englewood Cliffs, N.J.), 1969, pp. 117–151. MR 0246815
[10] C. Pomerance, Lecture notes on primality testing and factoring, MAA Notes No. 4 (1984).
[11] Carl Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete algorithms and complexity (Kyoto, 1986) Perspect. Comput., vol. 15, Academic Press, Boston, MA, 1987, pp. 119–143. MR 910929
[12] C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR 700260
[13] Hans Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR 897531
[14] René Schoof, Elliptic curves over finite fields and the computation of square roots mod 𝑝, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, https://doi.org/10.1090/S0025-5718-1985-0777280-6
[15] J. A. Serret, Sur un théorème rélatif aux nombres entières, J. Math. Pures Appl. 13 (1848), 12-14.
[16] 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
[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] Peter Wilker, An efficient algorithmic solution of the Diophantine equation 𝑢²+5𝑣²=𝑚, Math. Comp. 35 (1980), no. 152, 1347–1352. MR 583512, https://doi.org/10.1090/S0025-5718-1980-0583512-5