[Lagrange's four-squares theorem][1] states that every natural number can be represented as the sum of four integer squares. [Rabin and Shallit][2] 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][3]), but correct me if I am wrong.)


  [1]: https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem#cite_note-6
  [2]: https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem#Algorithms
  [3]: https://en.wikipedia.org/wiki/Jacobi%27s_four-square_theorem