01.12.2008

We design fast parallel deterministic algorithms (deterministic boolean NC) for interpolating arbitrary t-sparse polynomials over an arbitrary finite field GF[q][x₁,...,x_n]. The Interpolation Algorithm works in a slight field extension GF[q^{⌈2 log₇(nt)⌉ + 3}] and uses O(log³(nt)) boolean parallel time and O(n²t⁵log²nt) 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.