From: John Robertson Subject: Re: How Fast Can Computers Express p as x^2 + y^2? Date: Mon, 01 Jan 2001 16:13:17 GMT Newsgroups: sci.math In article , tpiezas@uap.edu.ph (Tito Piezas III) wrote: > Given p as a PRIME of the form 4m+1, how fast can a computer > express it as x^2 + y^2, supposing p is 100-digits long? > > Tito Piezas III There has been good discussion of this, but the following references might be of interest: Noam Elkies post on 4-16-00 to sci.math.research. Andrew Rockett and Peter Szusz, "Continued Fractions," World Scientific, 1992, pages 69-72. Gives a method based just on computing continued fraction expansion of sqrt(p), and one, already discussed in this thread, that starts by solving x^2 == -1 (mod p). Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, "An Introduction to the Theory of Numbers," Fifth Edition, John Wiley & Sons, Inc., New York, 1991. Exercise 6, sect 7.3, page 333. S. Wagon, The Euclidean Algorithm Strikes Again, American Mathematical Monthly, 97 (1990), pp 125-129. The method given in Rockett and Szusz based on computing cf expansion of sqrt(p)is not computationally as efficient as the methods that start by finding a solution to x^2 == -1 (mod p). See my post on May 4, 2000 to the Number Theory Listserver summarizing what is known about the length of the period of the cf expansion of sqrt(p). Nevertheless, this method in R&S might might be easier to implement in some situations. John Robertson Sent via Deja.com http://www.deja.com/