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
8519

01.12.2008

Efficient Deterministic Interpolation of Multivariate Polynomials over Finite Fields
Michael Clausen, Johannes Grabmeier and Marek Karpinski
[Download PostScript] [Download PDF]

We present an efficient interpolation scheme for n-variate k-sparse polynomials f over a finite field with q elements. The polynomial time interpolation algorithm uses 2k - ⌊(2k - 1)/q⌋ evaluations and is efficiently parallelizable (NC) within polynomial number of processors and squared-logarithmic parallel time.

Last Change: 12/01/08 at 18:22:20
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V