.svg){kind=logo}
REMARKS ON THE ALGORITHMS OF CORNACCHIA AND HERMITE-SERRET
Keywords:
binary quadratic forms, Cornacchia algorithm, Hermite-Serret algorithmDOI:
https://doi.org/10.17654/0972555522008Abstract
While it is well known that a prime of the form can be written as a sum of two squares, it is less well known that there are algorithms which produce the numerical value of the representation variables. Two of these algorithms appear to be efficient in actual computation. These algorithms, the Cornacchia and Hermite-Serret algorithms, are compared for speed by numerical experiment. The Hermite-Serret algorithm is generalized to other diagonal binary quadratic forms. Some non-diagonal binary quadratic forms are also considered and an algorithm to solve them is developed.
Received: January 5, 2022
Accepted: January 20, 2022
References
J. Basilla, On the solution of $x^2 + dy^2 = m$, Proc. Japan Acad. Ser. A Math. Sci. 80(A) (2004), 40-41.
J. Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), 1011-1013.
D. Cox, Primes of the form $x^2 + ny^2$, 2nd ed., John Wiley and Sons, Hoboken, 2013.
H. Davenport, The Higher Arithmetic, 8th ed., Cambridge University Press, Cambridge, 2008.
K. Hardy, J. Muskat and K. Williams, A deterministic algorithm for solving $n = fu^2 + gv^2$ in coprime integers u and v, Math. Comp. 55 (1990), 327-343.
K. Hardy, J. Muskat and K. Williams, Solving $n = au^2 + buv + cv^2$ using the Euclidean algorithm, Util. Math. 38 (1990), 225-236.
I. Niven, H. Zuckerman and H. Montgomery, An Introduction to the Theory of Numbers, John Wiley and Sons, New York, 1991.
R. Threlfall, A Probabilistic Public Key Encryption Scheme Based on Quartic Reciprocity, Retrieved Sept. 30, 2020. http://eprint.iacr.org/2020/353.
S. Wagon, The Euclidean algorithm strikes again, Amer. Math. Monthly 97 (1990), 125-129.
K. Williams, On finding the solutions of $n = au^2 + buv +cv^2$ in integers $u$ and $v$, Util. Math. 46 (1994), 3-19.
K. Williams, Some refinements of an algorithm of Brillhart, Canad. Math. Society Conference Proceedings 15 (1995), 409-416.
Downloads
Published
Issue
Section
License
Copyright (c) 2022 Pushpa Publishing House, Prayagraj, India
This work is licensed under a Creative Commons Attribution 4.0 International License.
_________________________________
Attribution: Credit Pusha Publishing House as the original publisher, including title and author(s) if applicable.
Non-Commercial Use: For non-commercial purposes only. No commercial activities without explicit permission.
No Derivatives: Modifying or creating derivative works not allowed without written permission.
Contact Pusha Publishing House for more info or permissions.
