A deterministic algorithm for solving $n=fu^ 2+gv^ 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 \[ \mathcal {O}({n^{1/4}}{(\log n)^3}(\log \log n)(\log \log \log n)),\] uniformly in f and g.
- 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, DOI https://doi.org/10.2307/2006975 W. S. Anglin, ${x^2} \equiv R$ $\pmod p$, Preprint, McGill University, 1987.
- John Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), 1011–1013. MR 314745, DOI https://doi.org/10.1090/S0025-5718-1972-0314745-6
- D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. MR 93504, DOI https://doi.org/10.1112/S0025579300001157 M. Cipolla, Un metodo per la risoluzione della congruenza di secondo grado, Rend. Accad. Sci. Fis. Mat. Napoli (3) 9 (1903), 154-163. 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. L. E. Dickson, History of the theory of numbers, vol. I, Chelsea, New York, 1952. C. Hermite, Note au sujet de l’article précédent, J. Math. Pures Appl. 13 (1848), 15.
- 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 C. Pomerance, Lecture notes on primality testing and factoring, MAA Notes No. 4 (1984).
- 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
- 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
- Hans Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR 897531
- René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI https://doi.org/10.1090/S0025-5718-1985-0777280-6 J. A. Serret, Sur un théorème rélatif aux nombres entières, J. Math. Pures Appl. 13 (1848), 12-14.
- 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 A. Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen, Gött. Nachr. (1891), 344-346. J. V. Uspensky and M. A. Heaslet, Elementary number theory, McGraw-Hill, New York, 1939.
- Peter Wilker, An efficient algorithmic solution of the Diophantine equation $u^{2}+5v^{2}=m$, Math. Comp. 35 (1980), no. 152, 1347–1352. MR 583512, DOI https://doi.org/10.1090/S0025-5718-1980-0583512-5
Retrieve articles in Mathematics of Computation with MSC: 11Y50, 11D09
Retrieve articles in all journals with MSC: 11Y50, 11D09
Additional Information
Article copyright:
© Copyright 1990
American Mathematical Society
