|
|
| |
| 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
|
University of Bonn -> Department of Computer Science -> Chair V | |