Abstract:
Deterministic algorithms are presented for the efficient solution of diagonal homogeneous equations in many variables over finite fields. As auxiliary algorithms, it is shown how to compute a field generator that is an nth power, and how to write elements as sums of nth powers, for a given integer n. All these algorithms take polynomial time in n and in the logarithm of the field size, and are practical as stated.

Click here for the full text (in PDF).

© ACM, 2005. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation (ISSAC'05, Beijing, China), July 2005, pp. 348-353, http://doi.acm.org/10.1145/1073884.1073932.