Algorithms
Michael O. Rabin and Jeffrey Shallit have found randomized polynomial-time algorithms for computing a representation n = x12 + x22 + x32 + x42 for a given integer n, in expected running time O((logn)2).
Read more about this topic: Lagrange's Four-square Theorem