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.

(I 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.)