PARI code analyzing whether given integer is presentable as sum of two integer squares

[Max Alekseyev]

On Nov 21, 2007 5:03 PM, Alexander Povolotsky <apovolot at gmail.com> wrote:

> Could anyone write/post PARI code (function) analyzing whether given
> integer is presentable as sum of two integer squares (finding all the
> combinations if more than one exist)?

Do you really need all the combinations or just their quantity?

This is a straightforward and somewhat slow printing out all such
unordered pairs:

{  sum2sq(n) = for(i=1,sqrtint(n\2),
if(issquare(n-i^2),print([i,sqrtint(n-i^2)])) ) }

E.g.:
? sum2sq(1000)
[10, 30]
[18, 26]
that should be interpreted as
1000 = 10^2 + 30^2 = 18^2 + 26^2.

If you are interested in just the quantity of such pairs, I have an
efficient implementation that relies on the prime factorization of a
given n. Hence, it may be slow for hard-to-factor integers (spending
most time in PARI's factor() routine) but very fast as soon as prime
factorization is found. I think can write similar code that not just
counts the number of representations but actually finds them (again
based on the prime factorization of n). The runtime complexity of this
code will be roughly equal to the complexity of (PARI's build-in
implementation of) prime factorization. Note that the complexity of
the code listed above is O(sqrt(n)) that corresponds to a very naive
and slow factorization algorithm that makes trial division for all
numbers below sqrt(n).

Max