Abstract. Litow & Davida (1988) show that inverses in large finite fields of small characteristic p say p = 2, can be computed by Boolean circuits of (order-optimal) logarithmic depth. We note that their numerical approach can also be implemented purely algebraically, and that the resulting much simpler algorithm yields, also for large p, both arithmetic and Boolean reductions of inversion in F_{p^n} to inversion in F_p. Back

Abstract. This paper analyzes the Euclidean algorithm and some variants of it for computing the greatest common divisor of two univariate polynomials over a finite field. The minimum, maximum and average number of arithmetic operations both on polynomials and in the ground field are derived. We consider five different algorithms to compute gcd(A_1, A_2) where A_1, A_2 in Z_2[x] have degrees m >= n >= 0. Compared with the classical Euclidean algorithm that needs on average 1/2 n + 1 polynomial divisions, two algorithms involving divisions need on average 1/3 n + O(1) and 1/4 n + O(1) polynomial divisions; two other algorithms use an average of 1/2 m + 1/3 n + O(1) and 1/4 m + 2/9 n + O(1) polynomial subtractions and no divisions. Back

Abstract. If g and h are polynomials of degrees r and s over a field, their functional composition f = g(h) has degree n = rs. The functional decomposition problem is: given f of degree n = rs, determine whether such g and h exist, and, in the affirmative case, compute them. We first deal with univariate polynomials, and present sequential algorithms that use O(n log^2 n log log n) arithmetic operations, and a parallel algorithm with optimal depth O (log n). Then we consider the case where f and h are multivariate, and g is univariate. All algorithms work only in the ``tame'' case, where the characteristic of the field does not divide r. Back

Abstract. If g and h are polynomials of degrees r and s over a field, their functional composition f = g(h) has degree n = rs. The functional decomposition problem is: given f of degree n = rs, determine whether such g and h exist, and, in the affirmative case, compute them. An apparently difficult case is when the characteristic p of the ground field divides r. This paper presents a polynomial-time partial solution for this ``wild'' case; it works, e.g., when p^2 | r. Back

Abstract. An efficient probabilistic algorithm to find a normal basis in a finite field is presented. It can, in fact, find an element of arbitrary prescribed additive order. It is based on a density estimate for normal elements. A similar estimate yields a probabilistic polynomial-time reduction from finding primitive normal elements to finding primitive elements. Back

Abstract. We compare the two computational models of Boolean circuits and arithmetic circuits in cases where they both apply, namely the computation of polynomials over the rational numbers or over finite fields. Over Q and finite fields, Boolean circuits can simulate arithmetic circuits efficiently with respect to size. Over finite fields of small characteristic, the two models are equally powerful when size is considered, but Boolean circuits are exponentially more powerful than arithmetic circuits with respect to depth. Most of the technical results given in this synopsis are taken from the literature. Back

Abstract. The connection between bilinear complexity and error-correcting codes, discovered by Brockett and Dobkin in 1973, yields lower bounds on the maximal ranks of tensors with a given shape. The resulting bounds are linear, and thus interesting only for ``unbalanced'' shapes like (n, n, 2) and (n,n, n^2 - k) with k <= n. As an example, for odd n the maximal rank of (n,n,2)-tensors is larger over Z_2 than over an algebraic closure of Z_2. Back

Abstract. If F_q is a finite field and f in F_q [x], then f is called a permutation polynomial if the mapping F_q \rightarrow F_q induced by f is bijective. This property can be tested by a probabilistic algorithm whose number of operations is polynomial (in fact, essentially linear) in the input size, i.e., in deg f · log q. This is extended to ``almost permutation polynomials,'' whose value set consists of almost all elements of F_q. Back

Abstract. Let q be a prime power, F_q a field with q elements, f in F_q [x] a polynomial of degree n >= 1, V(f) = # f (F_q) the number of different values f (a) of f, with a in F_q, and p = q - V (f). It is shown that either p = 0 or 4n^4 > q or 2pn > q. Hence, if q is ``large'' and f is not a permutation polynomial, then either n or p is ``large''. Back

Abstract. Optimal sequential and parallel algorithms for exponentiation in a finite field containing F_q are presented, assuming that qth powers can be computed for free. Back

Abstract. The processor-efficiency of parallel algorithms for exponentiation in a finite field extension is studied, assuming that a normal basis over the ground field is given. Back

Abstract. A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented. To factor a polynomial of degree n over F_q, the number of arithmetic operations in F_q is O((n^2 + n log q) · (log n)^2 log log n). The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored. Back

Abstract. In this paper, we discuss Niederreiter's algorithm for factoring polynomials over finite fields and compare it to Berlekamp's algorithm. Using Kaltofen and Saunder's version of Wiedemann's method for solving systems of linear equations, we present a probabilistic factorization algorithm. This approach is particularly interesting in characeristic two, where it seems somewhat faster than Kaltofen's adaptation of Berlekamp's factorization algorithm. Back

Abstract. Let F_q be a finite field with q elements, f in F_q (x) a rational function over F_q, and D \subseteq F_q the domain of definition of f. Consider three notions of ``permutation functions'': f is a permutation on F_q, or on D, or f is injective on D. For each of these, a random polynomial-time test is presented. For the image size of an arbitrary rational function, a fully polynomial-time randomized approximation scheme is given. Back

Abstract. Let F_q be a finite field with q elements and f in F_q (x) a rational function over F_q. No polynomial-time deterministic algorithm is known for the problem of deciding whether f induces a permutation on F_q. The problem has been shown to be in co- R \subseteq co-NP, and in this paper we prove that it is in R \subseteq NP and hence in ZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over F_q. Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem in ZPP unknown to be in P. A deterministic test and a simple probabilistic test for permutation functions are also presented. Back

Abstract. A homogeneous bivariate decomposition of a univariate polynomial f is of the form f = g(h,k) with polynomials g,h,k, where g is bivariate and homogeneous. Such decompositions are of interest in robotics applications. This paper gives a Structure Theorem relating these decompositions to certain block decompositions of the roots of f, decomposition algorithms, and a classification of all constellations of degrees for which ``almost all'' polynomials f have such a decomposition. Back

Abstract. Cyclic redundancy codes provide a simple yet useful tool for error-detection in data transmission over noisy channels. We present an efficient parallel algorithm for such codes. Back

Abstract. Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. The classical question of estimating the size of the image of a univariate polynomial is a special case. For curves given by sparse polynomials, the counting problem is # P-complete via probabilistic parsimonious Turing reductions. Back

Abstract. We show that in a prime finite field F_p all rational points on a plane curve of a fixed degree can be found in time O ~(n^{O(1)} p) (i.e. in ``polynomial time per a point'') Back

Abstract. It is shown that Gauß periods of a special type give an explicit polynomial-time computation of elements of exponentially large multiplicative order in some finite fields. This can be considered as a step towards solving the celebrated problem of finding primitive roots in finite fields in polynomial time. Back

Abstract. This paper studies computational aspects of the basic algebraic and combinatorial properties of algebraic curves over finite fields: the number of points on a curve or a projection, its number of absolutely irreducible components, and the property of being ``exceptional''. Back

Abstract. Gauß periods yield (self-dual) normal bases in finite fields, and these normal bases can be used to implement arithmetic efficiently. It is shown that for a small prime power q and infinitely many integers n, multiplication in a normal basis of F_{q^n} over F_q can be computed with O(n log n loglog n), division with O(n log^2 n loglog n) operations in F_q, exponentiation of an arbitrary element in F_{q^n} can be done with O(n^2 loglog n) operations in F_q. The previous best estimates were O(n^2) for multiplication in a normal basis, and O(n^2 log n loglog n) for exponentiation in a polynomial basis. Back

Abstract. This paper gives an algorithm to factor a polynomial f (in one variable) over residue class rings of Z or Fq[y]. The Chinese Remainder Theorem reduces our problem to the case where r is a prime power. Then factorization is not unique, but if r does not divide the discriminant of f, our (probabilistic) algorithm produces a description of all (possibly exponentially many) factorizations into irreducible factors in polynomial time. If r divides the discriminant, we only know how to factor by exhaustive search, in exponential time. Back

Abstract. We describe algorithms for polynomial multiplication and polynomial factorization over the binary field F_2 and their implementation. They allow polynomials of degree up to 100,000 to be factored in about one day of CPU time, distributing the work on two machines. Back Postscript Full version (Technical report tr-rsfb-96-018, University of Paderborn, Germany, 1996, 43 pages)

Abstract. Given two integers a and k, for any prime p not dividing a with p \equiv 1 mod k, we denote by ind_p (a) the index of a mod p. In [G-G-P] it was raised the question of calculating the density of the primes p for which ind_p (a) and (p-1)/k are coprime. We assume the Generalized Riemann Hypothesis and calculate a formula for such a density for all given a and k. We prove unconditionally that our formula is an upper bound for the density and then express it as an Euler product. Back

Abstract. We analyze six algorithms for computing integral Taylor shifts for polynomials with integral coefficients. We present and analyze a new algorithm for solving the ``key equation'' which occurs in many rational and hypergeometric summation algorithms. In a special case, our algorithm is asymptotically faster than previously known methods. We give experimental results for our algorithms. Back Postscript

Abstract. A polynomial f in F_q [x], over a finite field F_q with q elements, is p-large if its image in F_q contains at least q - p elements. This Extended Abstract presents an efficient probabilistic test for this property, using expected time polynomial in deg f, log q, and p. Back

Abstract. Optimal sequential and parallel algorithms for exponentiation in a finite field extension are presented, assuming that a normal basis over the ground field is given. Back

Abstract. Let F_q be a finite field with q elements and f in F_q (x) a rational function over F_q. No polynomial-time deterministic algorithm is known for the problem of deciding whether f induces a permutation on F_q. The problem has been shown to be in co- R \subseteq co-NP, and in this paper we prove that it is in R \subseteq NP and hence in ZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over F_q. Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem in ZPP unknown to be in P. A deterministic test and a simple probabilistic test for permutation functions are also presented. Back

Abstract. A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. To factor a polynomial of degree n over F_q, the algorithm uses O((n^2 + n log q) · (log n)^2 loglog n) arithmetic operations in F_q. The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored. Back

Abstract. Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. Classical questions on estimating the size of the image of a univariate polynomial are special cases. For sparse polynomials, the counting problem is # P-complete via probabilistic Turing reductions, under an unproven number-theoretical assumption. Back

Abstract. Let F_q be a finite field with q elements, f = g/h a rational function over F_q, and D (f) the domain of definition of f. Consider three notions of ``permutation functions'': f is a permutation on F_q, or on D (f), or f is injective on D (f). For each of these, a random polynomial time test is presented. For arbitrary rational functions, a fully polynomial (epsilon, delta)-approximation scheme for the image size is given. Back

Abstract. Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. Classical questions on estimating the size of the image of a univariate polynomial are special cases. For sparse polynomials, the counting problem turns out to be # P-complete via probabilistic Turing reductions, under an unproven number-theoretical assumption. Joint work with Marek Karpinski and Igor Shparlinski. Back

Abstract. Let F_q be a finite field with q elements and f in F_q (x) a rational function over F_q. No polynomial-time deterministic algorithm is known for the problem PermFunction of deciding whether f induces a permutation on F_q. The problem has been shown to be in co- R \subseteq co- NP, and in this paper we prove that it is in R \subseteq NP and hence in ZPP, and it is deterministic polynomial-time reducible to the problem PolyFactor of factoring univariate polynomials over F_q. Besides the problem Prime of recognizing prime numbers, it seems to be the only natural decision problem in ZPP unknown to be in P. A deterministic test and a simple probabilistic test for permutation functions are also presented. Back

Abstract. This Extended Abstract studies computational aspects of the basic algebraic and combinatorial properties of algebraic curves over finite fields: the number of points on a curve or a projection, its number of absolutely irreducible components, and the property of being ``exceptional''. Back

Abstract. Gauss periods can be used to implement finite field arithmetic efficiently. For a small prime p and infinitely many integers n, exponentiation of an arbitrary element in F_{p^n} can be done with O(n^2 loglog n) operations in F_p, and exponentiation of a Gauss period with O(n^2) operations in F_p. Comparing to the previous estimate O(n^2 log n loglog n), using polynomial bases, this shows that normal bases generated by Gauss periods offer some asymtotic computational advantage. Experimental results indicate that Gauss periods are often primitive elements in finite fields. Back

Abstract. We solve two computational problems concerning plane algebraic curves over finite fields: generating an (approximately) uniform random point, and finding all points deterministically in amortized polynomial time(over a prime field, for non-exceptional curves). Back

Abstract. Gauß periods have been used successfully as a tool for constructing normal bases in finite fields. Starting from a primitive rth root of unity, one obtains under certain conditions a normal basis for F_{q^n} over F_q, where r is a prime and nk=r-1 for some integer k. We generalize this construction by allowing arbitrary integers r with nk=phi(r), and find in many cases smaller values of k than is possible with the previously known approach. Back