From: shallit@graceland.waterloo.edu (Jeffrey Shallit) Newsgroups: sci.math.numberthy Subject: expressing n as a sum of four squares Date: 5 Jun 92 13:55:08 GMT Sender: NMBRTHRY@VM1.NoDak.EDU Michael Rabin and I (with hints from Andrew Odlyzko) showed how to express any positive integer n as a sum of four squares in random polynomial time. Consult "Randomized algorithms in number theory", Commun. Pure Appl. Math. V. 39, No. S (1986), S239-S256. Note this is a special supplementary issue of the journal. Relatively recent (1990) and still unpublished (to my knowledge) results of R. Bumby give a deterministic polynomial time algorithm in the case that n is prime. Computing the NUMBER of such representations (as sums of four squares) is random polynomial-time equivalent to factoring n. Jeff Shallit shallit@graceland.waterloo.edu ============================================================================== From: U21453@UICVM.BITNET (A.O.L.Atkin 312 413-2155) Newsgroups: sci.math.numberthy Subject: Four Squares(more) Date: 5 Jun 92 13:55:15 GMT Sender: NMBRTHRY@VM1.NoDak.EDU The two replies of Ben-Or and myself illustrate perfectly the distinction between computer science and practical mathematics. I realize that to be randomly correct is an essential part of computational correctness, but I cannot believe that any serious number theorist who actually uses a machine would adopt Ben-Or's algorithm as it is stated. One may also observe that if N is divisible by 4,the O(1/ log N ) probability quoted has a remarkably bad constant(or should I say good ?) . In the circumstances,I had better fill out my previous note. If one can represent N as four squares,one can represent 4N. If one can represent 4N+2 one can represent 2N+1. Hence to do 4N+2 is enough. Now make a list of ALL 4m+1 from m=1 to (say)100000; cross out those which are not two squares using primes = 3(mod 4);cross out those for which 4N+2-(4m+1) is divisible by any prime less than (say) 10000. Be careful not to overkill if N is small. At this point do a Selfridge strong psp test with base 2(not a pseudorandom base!)on the remaining candidates. When a presumptive prime is found,express both this"prime"and the (4m+1) as a sum of two squares(we do not need to prove that the "prime" is prime.) If we cannot do so(& so have proved that the "prime" was composite),try again. oa