Lagrange's four-squares theorem states that every natural number can be represented as the sum of four integer squares. Rabin and Shallit gave a randomised algorithm that finds one of these solutions in quadratic time. My question is if anything is known about the *deterministic* time complexity of finding one of the solutions? Any pointers would be appreciated.

(It seems that *enumerating* all the solutions is hard as factoring in certain cases (via Jacobi's four-square theorem), but correct me if I am wrong.)