From: shallit@graceland.uwaterloo.ca (Jeffrey Shallit)
Subject: Re: Sum of 4 Squares
Date: 19 Jul 2001 01:45:20 GMT
Newsgroups: sci.math
Summary: Writing integers as sums of three or four squares
In article ,
Stush wrote:
>I'm looking for an algorithm no express any integer as the sum of four
>square, i.e.
>
>Given n, find a,b,c,d such that
>n = a^2 + b^2 + c^2 + d^2
>
>Thanks
See my paper with Michael Rabin,
``Randomized algorithms in number theory'',
Commun. Pure and Appl. Math. 39 (1986), S239--S256, which gives
an efficient algorithm.
Jeffrey Shallit, Computer Science, University of Waterloo,
Waterloo, Ontario N2L 3G1 Canada shallit@graceland.uwaterloo.ca
URL = http://www.math.uwaterloo.ca/~shallit/
==============================================================================
From: alpertron@hotmail.com (Dario Alpern)
Subject: Re: Number = Sum of squares
Date: 10 Oct 2001 17:44:53 -0700
Newsgroups: sci.math
alpertron@hotmail.com (Dario Alpern) wrote in message news:<1abc6a46.0109251419.e8249fb@posting.google.com>...
> Hello all,
>
> I've just added a new feature to my ECM Online Factorization
> Calculator that shows a decomposition of the number input by the user
> in a sum of up to four squares.
>
> For example, the number
> 54637856487946327819463278149637281496327814963278196437819654 can be
> written as a^2 + b^2 + c^2 + d^2 where
>
> a = 6 108077 345747 128026 678719 165288
> b = 3 132268 970255 734978 111786 108799
> c = 2 731336 010938 625315 377818 001553
> d = 240712 109458 586493 590653 571750
>
> The address is:
>
> http://www.alpertron.com.ar/ECM.HTM
>
When a number does not have the form 4^a * (8*m+7) (where a>=0), it
can be expressed as a sum of three squares.
Now the applet is able to show the sum of three squares.
Using the same example shown above, the number can be written as a^2 +
b^2 + c^2 where:
a = 6 168255 775036 150097 322585 356374
b = 4 073140 947926 981706 465481 896717
c = 117
Best regards,
Dar�o Alejandro Alpern
Buenos Aires - Argentina
http://www.alpertron.com.ar/ENGLISH.HTM