Joachim von zur Gathen
- 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.
previous
next
Anmerkungen/Anregungen bitte an
webmaster@math.uni-paderborn.de
Datum : 16.07.01