|
|
| |
| 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
|
Universität Bonn -> Institut für Informatik -> Abteilung V | |