A deterministic algorithm for solving $n=fu^ 2+gv^ 2$ in coprime integers $u$ and $v$
HTML articles powered by AMS MathViewer
- by Kenneth Hardy, Joseph B. Muskat and Kenneth S. Williams PDF
- Math. Comp. 55 (1990), 327-343 Request permission
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.References
- 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 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 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 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. America, Buffalo, N.Y.; 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, DOI 10.1007/978-1-4757-1089-2
- 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 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) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. 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 10.1090/S0025-5718-1980-0583512-5
Additional Information
- © Copyright 1990 American Mathematical Society
- 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