There is a *deterministic* polynomial-time algorithm for finding solutions to diagonal equations of degree less than or equal to the number of variables over finite fields.  See [Christiaan van de Woestijne's thesis][1].

(A solution of your example equation can be found much more simply, however: try small integers, not necessarily distinct... .  And for quadratic forms, the other solutions can be found by drawing lines through the point and intersecting with the quadric hypersurface: there will either be one more intersection point, or a whole line of points.)


  [1]: http://www.opt.math.tugraz.at/~cvdwoest/