Department of Computer Science
Chair V

University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V


Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
Dima Grigoriev, Marek Karpinski and Michael F. Singer
[Download PostScript] [Download PDF]

We design fast parallel deterministic algorithms (deterministic boolean NC) for interpolating arbitrary t-sparse polynomials over an arbitrary finite field GF[q][x1,...,xn]. The Interpolation Algorithm works in a slight field extension GF[q⌈2 log7(nt)⌉ + 3] and uses O(log3(nt)) boolean parallel time and O(n2t5log2nt) processors. It is the first efficient deterministic polynomial time algorithm (and moreover boolean NC-algorithm) for this problem, and together with the efficient deterministic interpolation algorithms for fields of characteristic 0 (cf.[GK 87], [BT 88]) yields for the first time the general deterministic sparse conversion algorithm working over arbitrary fields. (The reason for this is that every field of positive characteristic contains a primitive subfield of this characteristics, and so we can apply our method to the slight extension of this subfield). The method of solution involves the polynomial enumeration techniques of [GK 87] combined with introducing a new general method of breaking the problem of identity to zero of sparse polynomials over the (logarithmic) slight field extension.

Last Change: 12/01/08 at 19:26:58
University of Bonn -> Department of Computer Science -> Chair V