A modification of Dror's comment.
This probabilistic algorithm worked for me.
The main idea is to pick some $z$, compute $m=n - z^2$, factor $m$ with trial division and express it as a sum of two squares if possible. The probability of finding prime $m=4a+1$ or $2p$ is high enough for practical purposes.
The algorithm:
- z:=0
- z:=z+1
- m:=n-z^2
- if can't trial factor m goto 2
- if m=x^2+y^2 (the factorization is known) then x^2+y^2+z^2=n. Done
- goto 2