**Counting curves and their projections**`(GnuZip(.ps), 107132 Byte, Author: Joachim von zur Gathen (Toronto), Marek Karpinski (Bonn), and Igor Shparlinski (Sydney), 5 June 1994)`

**Components and projections of curves over finite fields**`(GnuZip(.ps), 82266 Byte, Author: Joachim von zur Gathen (Toronto) and Igor Shparlinski (Sydney), 7 July 1995)`

**Finding points on curves over finite fields**`(GnuZip(.ps), 79106 Byte, Author: Joachim von zur Gathen (Toronto) and Igor Shparlinski (Sydney), 6 November 1995)`

**Orders of Gauss periods in finite fields**`(GnuZip(.ps), 47297 Byte, Author: Joachim von zur Gathen (Paderborn) and Igor Shparlinski (Sydney), 17 June 1996)`

It is shown that Gauss 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.**Homogenous bivariate decompositions**`(GnuZip(.ps), 102710 Byte, Author: Joachim von zur Gathen (Toronto) and Jürgen Weiss (Bonn), 6 January 1995)`

**Gauss periods, primitive normal bases, and fast exponentiation in finite fields**`(GnuZip(.ps), 64313 Byte, Author: Shuhong Gao (Clemson), Joachim von zur Gathen (Paderborn), and Daniel Panario (Toronto), 2 August 1995)`

with Appendix**Deterministic factorization of polynomials over special finite fields**`(GnuZip(.ps), 47405 Byte, Author: Eric Bach (Madison), Joachim von zur Gathen (Toronto), and Hendrik W. Lenstra, Jr. (Berkeley), 28 February 1995)`

**Polynomials with two values**`(GnuZip(.ps), 70294 Byte, Author: Joachim von zur Gathen (Toronto) and James R. Roche (Bell Laboratories), 23 September 1993)`

**Arithmetic and factorization of polynomials over F_2**`(GnuZip(.ps), 203836 Byte, Author: Joachim von zur Gathen (Paderborn) and Juergen Gerhard (Paderborn), 14 June 1996)`

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.**Factoring modular polynomials**`(GnuZip(.ps), 100086 Byte, Author: Joachim von zur Gathen (Paderborn) and Silke Hartlieb (Paderborn), 13 May 1996)`

This paper gives an algorithm to factor a polynomial f (in one variable) over residue class rings of Z or F_q[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.**Factorization of polynomials modulo small prime powers**`(GnuZip(.ps), 49839 Byte, Author: Joachim von zur Gathen (Paderborn) and Silke Hartlieb (Paderborn), 16 July 1996)`

This paper describes an algorithm for factoring polynomials over residue class rings of Z or F_q[y], in the ``difficult'' case where we want to factor modulo a prime power which divides the discriminant of the polynomial, i.e., the discriminant of the polynomial is zero in the residue class ring. The method works in exponential time.**Normal bases via general Gauss perions**`(GnuZip(.ps), 136742 Byte, Author: Joachim von zur Gathen (Paderborn) and Sandra Schlink (Paderborn), June 1996)`

This paper gives a survey on the State of the Art in the area of normal basis arithmetic in finite fields and generalizes the construction of Gauss periods in that instead of a prime nk+1 an arbitrary integer r>1 with phi(r)=nk is used. It turns out that this construction yields in some cases smaller values of k than is possible with the previously known method.**On polynomial approximation and the parallel complexity of the discrete logarithm and breaking the Diffie-Hellman cryptosystem**`(GnuZip(.ps), 93669 Byte, Author: Igor Shparlinski (Sydney), 3 July 1996)`

Several exponential (in terms of log p) lower bounds are obtained on the degrees and orders of

- polynomials;

- algebraic functions;

- Boolean functions;

- lrs{s}

coinciding with values of the dl modulo a prime $p$ at sufficiently many points (the number of point can be as little as $p^{1/2 + varepsilon}$ or more points). These functions are considered over the residue ring modulo $p$ and over the residue ring modulo an arbitrary divisor $d$ of $p-1$.; the case of $d=2$ is of special interest since it corresponds to the representation of the last bit of dl and defines wether the argument is a quadratic residue. These bounds are used to obtain lower bounds on parallel complexity of computing dl.

The method is based on bounds of character sums and numbers of solutions of some polynomial equations.

Similar results are obtained for breaking the Diffie-Hellman cryptosystem. Several other applications of the method are pointed out as well.

Anmerkungen/Anregungen bitte an webmaster@math.uni-paderborn.de

Datum : 16.07.01