Christiaan van de Woestijne
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.
- Leonard Adleman, Kenneth Manders, and Gary Miller. On taking roots in finite fields. In 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977), pages 175--178. IEEE Comput. Sci., Long Beach, Calif., 1977.Google Scholar
Digital Library
- Eric Bach. A note on square roots in finite fields. IEEE Trans. Inform. Theory, 36(6):1494--1498, 1990.Google ScholarDigital Library
- Eric Bach, Joachim von zur Gathen, and Hendrik~W. Lenstra, Jr. Factoring polynomials over special finite fields. Finite Fields Appl., 7(1):5--28, 2001. Dedicated to Professor Chao Ko on the occasion of his 90th birthday. Google ScholarDigital Library
- Henri Cohen. A course in computational algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1993. Google ScholarDigital Library
- V. B. Dem′yanov. On representation of a zero of forms of the form ∑ m i=1a ix i n. Dokl. Akad. Nauk SSSR (N.S.), 105:203--205, 1955.Google Scholar
- G.H. Hardy and E.M. Wright. An introduction to the theory of numbers. Oxford, at the Clarendon Press, 1965. Fourth edition, 3rd corrected printing.Google Scholar
- Jean-René Joly. Équations et variéé algébriques sur un corps fini. Enseignement Math. (2), 19:1--117, 1973.Google Scholar
- T. Y. Lam. The algebraic theory of quadratic forms. W. A. Benjamin, Inc., Reading, Mass., 1973. Mathematics Lecture Note Series.Google Scholar
- H. W. Lenstra, Jr. Finding isomorphisms between finite fields. Math. Comp., 56(193):329--347, 1991.Google ScholarCross Ref
- René Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp., 44(170):483--494, 1985.Google Scholar
- Štefan Schwarz. On universal forms in finite fields. Časopis Pěst. Mat. Fys., 75:45--50, 1950.Google Scholar
- Daniel Shanks. Five number-theoretic algorithms. In Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972), pages 51--70. Congressus Numerantium, No. VII, Winnipeg, Man., 1973. Utilitas Math.Google Scholar
- Charles Small. Diagonal equations over large finite fields. Canad. J. Math., 36(2):249--262, 1984.Google ScholarCross Ref
- Alberto Tonelli. Bemerkung Über die Auflösung quadratischer Congruenzen. Nachr. Göttingen, (10):344--346, 1891. Reported in Dickson's History, Vol. 1, Ch. VII, item 193, p. 215.Google Scholar
- Leonard Tornheim. Sums of n-th powers in fields of prime characteristic. Duke Math. J., 4:359--362, 1938.Google ScholarCross Ref
- Joachim von zur Gathen and Jürgen Gerhard. Modern computer algebra. Cambridge University Press, Cambridge, second edition, 2003. Google ScholarDigital Library
- André Weil. Numbers of solutions of equations in finite fields. Bull. Amer. Math. Soc., 55:497--508, 1949.Google ScholarCross Ref
- Arne Winterhof. On Waring's problem in finite fields. Acta Arith., 87(2):171--177, 1998.Google ScholarCross Ref
Index Terms
- Deterministic equation solving over finite fields
Recommendations
Efficient and accurate finite difference schemes for solving one-dimensional Burgers' equation
In this paper, two efficient fourth-order compact finite difference algorithms have been developed to solve the one-dimensional Burgers' equation: ut+u ux=ε uxx. The methods are based on the Hopf-Cole transformation, Richardson's extrapolation, and ...
Solving systems of diagonal polynomial equations over finite fields
We present an algorithm to solve a system of diagonal polynomial equations over finite fields when the number of variables is greater than some fixed polynomial of the number of equations whose degree depends only on the degree of the polynomial ...
Characteristic set algorithms for equation solving in finite fields
Efficient characteristic set methods for computing zeros of polynomial equation systems in a finite field are proposed. The concept of proper triangular sets is introduced and an explicit formula for the number of zeros of a proper and monic triangular ...
Comments