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