REMARKS ON THE ALGORITHMS OF CORNACCHIA AND HERMITE-SERRET
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.
binary quadratic forms, Cornacchia algorithm, Hermite-Serret algorithm.
Received: January 5, 2022; Accepted: January 20, 2022; Published: February 4, 2022
How to cite this article: Jesse Ira Deutsch, Remarks on the algorithms of Cornacchia and Hermite-Serret, JP Journal of Algebra, Number Theory and Applications 53(2) (2022), 137-149. DOI: 10.17654/0972555522008
This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License
References:
[1] J. Basilla, On the solution of x2 + dy2 = m, Proc. Japan Acad. Ser. A Math. Sci. 80(A) (2004), 40-41.[2] J. Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), 1011-1013.[3] D. Cox, Primes of the form x2 + ny2, 2nd ed., John Wiley and Sons, Hoboken, 2013.[4] H. Davenport, The Higher Arithmetic, 8th ed., Cambridge University Press, Cambridge, 2008.[5] K. Hardy, J. Muskat and K. Williams, A deterministic algorithm for solving n = fu2 + gv2 in coprime integers u and v, Math. Comp. 55 (1990), 327-343.[6] K. Hardy, J. Muskat and K. Williams, Solving n = au2 + buv + cv2 using the Euclidean algorithm, Util. Math. 38 (1990), 225-236.[7] I. Niven, H. Zuckerman and H. Montgomery, An Introduction to the Theory of Numbers, John Wiley and Sons, New York, 1991.[8] R. Threlfall, A Probabilistic Public Key Encryption Scheme Based on Quartic Reciprocity, Retrieved Sept. 30, 2020. http://eprint.iacr.org/2020/353.[9] S. Wagon, The Euclidean algorithm strikes again, Amer. Math. Monthly 97 (1990), 125-129.[10] K. Williams, On finding the solutions of n = au2 + buv +cv2 in integers u and v, Util. Math. 46 (1994), 3-19.[11] K. Williams, Some refinements of an algorithm of Brillhart, Canad. Math. Society Conference Proceedings 15 (1995), 409-416.
