Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope