We present counting methods for some special classes of multivariate polynomials over a finite field, namely, the reducible ones, the $s$-powerful ones (divisible by the $s$th power of a nonconstant polynomial), and the relatively irreducible ones (irreducible but reducible over an extension field). One approach employs generating functions, and another one uses a combinatorial method. They yield exact formulas and approximations with relative errors that essentially decrease exponentially in the input size.

A univariate polynomial f over a field is decomposable if f = g o h = g(h) for nonlinear polynomials g and h. In order to count the decomposables, one wants to know the number of equal-degree collisions of the form f = g o h = g* o h* with (g, h) ≠ (g*, h*) and deg g = deg g*. Such collisions only occur in the wild case, where the field characteristic p divides deg f. Reasonable bounds on the number of decomposables over a finite field are known, but they are less sharp in the wild case, in particular for degree p2.

International audience

The functional decomposition of polynomials has been a topic of great interest and importance in pure and computer algebra and their applications. The structure of compositions of (suitably normalized) polynomials f = g o h in Fq[x] is well understood in many cases, but quite poorly when the degrees of both components are divisible by the characteristic p. This work investigates the decomposition of polynomials whose degree is a power of p. An (equal-degree) i-collision is a set of i distinct pairs (g, h) of polynomials, all with the same composition and deg g the same for all (g, h). Abhyankar (1997) introduced the projective polynomials xn+ ax + b, where n is of the form (rm -- 1)/(r -- 1) and r is a power of p. Our first tool is a bijective correspondence between i-collisions of certain additive trinomials, projective polynomials with i roots, and linear spaces with i Frobenius-invariant lines.

A univariate polynomial f over a field is decomposable if it is the composition f = g ⊕ h of two polynomials g and h whose degree is at least 2. We determine an approximation to the number of decomposable polynomials over a finite field. The tame case, where the field characteristic p does not divide the degree n of f, is reasonably well understood, and we obtain exponentially decreasing error bounds.The wild case, where p divides n, is more challenging and our error bounds are weaker. A centerpiece of our approach is a decomposition algorithm in the wild case, which shows that sufficiently many polynomials are decomposable.

Among the bivariate polynomials over a finite field, most are irreducible. We count some classes of special polynomials, namely the reducible ones, those with a square factor, the "relatively irreducible" ones which are irreducible but factor over an extension field, and the singular ones, which have a root at which both partial derivatives vanish.

No abstract available.

We study different possibilities of implementing Karatsuba multipliers for polynomials over F2on Field Programmable Gate Arrays (FPGAs). This is a core task for implementing finite fields of characteristic 2. Algorithmic and platform dependent optimizations yield efficient hardware designs. The resulting structure is hybrid in two different aspects. On the one hand, a combination of various methods decreases the number of bit operations. On the other hand, a mixture of sequential and combinational circuit design techniques including pipelining is used to design a circuit which can be adapted flexibly to time-area constraints. The approach—both theory and implementation—can be viewed as a further step towards taming the machinery of fast algorithmics for hardware applications.

We describe an authentication scheme whose security is based on the hardness of finding roots of systems of sparse polynomial equations in many variables and of high degree. One of the new ideas is the use of many keys. In one authentication session, a small amount of information about only one of them, chosen randomly, is released; this may be useful in other situations as well. Although the practicality of this scheme has still to be investigated, we believe that the new ideas described here may be of independent interest.

We solve two computational problems concerning plane algebraic curves over finite fields: generating a uniformly random point, and finding all points deterministically in amortized polynomial time (over a prime field, for nonexceptional curves).

A necessary criterion for irreducibility of a trinomial over a finite field, based on classical results of Stickelberger and Swan, is established. It is applied in the special case F3.

One of the long-standing open questions in the theory of parallel computation is the parallel complexity of the integer gcd and related problems, such as modular inversion. We present a lower bound $\Omega (\log n)$ for the parallel time on a concurrent-read exclusive-write parallel random access machine (CREW PRAM) computing the inverse modulo certain n-bit integers, including all such primes. For infinitely many moduli, our lower bound matches asymptotically the known upper bound. We obtain a similar lower bound for computing a specified bit in a large power of an integer. Our main tools are certain estimates for exponential sums in finite fields.

We study exponentiation in finite fields with very special exponents such as they occur, e.g., in inversion and in primit.ivitytests.Our algorit.hmicapproach improves the corrcspending exponentiation problem from about qimtlratic to about liIM!ifl time.

This paper provides an algorithmic approach to some 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."

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 asymp totically faster than previously known methods.We give experimental results for our algorithms.

We describe algorithms for polynomial multiplication and polynomial factorization over the binary field IF2.and their implementation.They allow polynomials of degree up to 100,000 to be factored in about one dqy of CPU time.

This paper gives analgorithm to factor apolynomialf (in one variable) over residue class rings of ZoriFq [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) factorization into irreducible factors in polynomial time.If ~divides the discriminant, we only know how to factor by exhaustive search, in exponential time.

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).

Let\(\mathbb{F}_q \) be a finite field withq elements and\(f \in \mathbb{F}_q \left( x \right)\) a rational function over\(\mathbb{F}_q \). No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on\(\mathbb{F}_q \). The problem has been shown to be in co-R\( \subseteq \)co-NP, and in this paper we prove that it is inR\( \subseteq \)NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over\(\mathbb{F}_q \). Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented.

. 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. 1. Introduction One of the most celebrated results in algebraic geometry is Weil's theorem on the number of points on algebraic curves over a finite field. In this paper, we address some computational problems related to this question. Our main results are: ffi A "computational Weil estimate" for projections of curves and images of polynomials, in Section 3. ffi #P-completeness of the exact counting problem for sparse curves, in Section 4. We consider a finite field F q with q elements, an algebraic closure K of F q , a polynomial f 2 F q [x; y] of degree n , the plane curve C = ff = 0g = f(a;...

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 Fq, the algorithm uses O((n2 + n log q)•(log n)2 log log n) arithmetic operations in Fq. 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.

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.>

If $\mathbb{F}_q $ is a finite field and $f \in \mathbb{F}_q [x]$, then f is called a permutation polynomial if the mapping $\mathbb{F}_q \to \mathbb{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 \cdot \log q$. This is extended to “almost permutation polynomials,” whose value set consists of almost all elements of $\mathbb{F}_q $.

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

The simple test for determining whether an arbitrary polynomial is a permutation polynomial, by producing its list of values, is considered, and it is found that off-the-shelf techniques from computer algebra improve the running time slightly, without requiring any new insights into the problem. A probabilistic variant of the Hermite test that reduces its running time is given. A criterion for permutation polynomials is then examined, and a probabilistic test whose number of operations is essentially linear in the input size is then given. Exceptional polynomials, which are closely related to permutation polynomials, are also considered, and a random polynomial-time test for these is described.>

ABSTRACT NOT AVAILABLE

Fast parallel computations are presented for large powers modulo an element that has only small prime factors. They work for integers and polynomials over small finite fields.

The n × n-permanent is not a projection of the m × m-determinant if m ≤ √8/7 n - 1.

Representations of univariate rational functions over a given base of polynomials are considered, and a fast parallel algorithm for converting from one base representation to another is given. Special cases of this conversion include the following symbolic manipulation problems: Taylor expansion, partial fraction decomposition, Chinese remainder algorithm, elementary symmetric functions, Padé approximation, and various interpolation problems. If n is the input size, then all algorithms run in parallel time $O(\log ^2 n)$ and use $n^{O(1)} $ processors. They work over an arbitrary field.

A fast parallel computation for large powers of an integer module another integer is presented, assuming that the modulus has only small prime factors

Fast parallel algorithms are presented for the following problems in symbolic manipulation of univariate polynomials: computing all entries of the extended Euclidean scheme of two polynomials over an arbitrary field, gcd and 1cm of many polynomials, factoring polynomials over finite fields, and the squarefree decomposition of polynomials over fields of characteristic zero and over finite fields. For the following estimates, assume that the input polynomials have degree at most n, and the finite field has $p^d $ elements. The Euclidean algorithm is deterministic and runs in parallel time $O(\log ^2 n)$. All the other algorithms are probabilistic (Las Vegas) in the general case, but when applicable to ${\bf Q}$ or ${\bf R}$, they can be implemented deterministically over these fields. The algorithms for gcd and lcm use parallel time $O(\log ^2 n)$. The factoring algorithm runs in parallel time $O(\log ^2 n\log ^2 (d + 1)\log p)$. The algorithm for squarefree decomposition runs in parallel time $O(\log ^2 n)$ for characteristic zero, and in parallel time $O(\log ^2 n+(d - 1)\log p)$ for finite fields. All Las Vegas algorithms have failure probability less than $2^{ - n} $. For all algorithms, the number of processors is polynomial in n.

Fast parallel algorithms for various problems in algebraic computation are presented. Two of the algorithms convert the coefficient representation of a rational function into a base representation, and vice versa. Combining them yields an algorithm which converts the representation of a rational function in one base of polynomials into that in another base. The existence question for representations is then discussed. Applications of the general conversion algorithms fast parallel methods to Taylor expansion, partial fraction decomposition, Chinese remainder algorithm, elementary symmetric functions, Pade approximation and various interpolation problems are given. 5 references.

In Borodin-von zur Gathen-Hopcroft[82] the following program is laid out: obtain a “theory package for parallel algebraic computations”, i.e. fast parallel computations for the widely used problems of symbolic manipulation in an algebraic context. In that paper, two basic problems were considered: solving systems of linear equations and computing the gcd of two polynomials, both over arbitrary ground fields.

We present parallel algorithms to compute the determinant and characteristic polynomial of n×n-matrices and the gcd of polynomials of degree ≤n. The algorithms use parallel time O(log2n) and a polynomial number of processors. We also give a fast parallel Las Vegas algorithm for the rank of matrices. All algorithms work over arbitrary fields.