On the computation of representations of primes as sums of four squares

Lagrange proved that every positive integer is the sum of four squares of natural numbers. Although Lagrange’s proof is constructive, it is not known whether the relative algorithm produces a four-square represen-tation of any prime or non-prime integer with deterministic polynomial complexity. Limited to prime numbers, it is proved that their repre-sentation as the sums of four squares can be obtained with determinis-tic polynomial complexity. The key to this computational accomplish-ment is the evaluation of square roots modulo a prime, through Schoof’s method for counting the number of points on elliptic curves over prime fields.