Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
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?)


Similar Articles

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

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


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1990-1023762-3
PII: S 0025-5718(1990)1023762-3
Article copyright: © Copyright 1990 American Mathematical Society