Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4609043 | Journal of Complexity | 2007 | 10 Pages |
Abstract
In this paper we present explicit vector formulae for the Lagrange–Newton transformation L:Kn→Kn and its inverse L-1 with respect to interpolating knots xi=αxi-1+β(i=1,2,…,n-1;x0=γ), where α≠0,β,γ belong to a field K. These formulae depend on the wrapped convolution, Horner transformation, iterative product and coordinatewise vector operations. All these transformations and operations, except of O(nlogn)—wrapped convolution, have running time of O(n) base operations from the field K. Moreover, we give an application of these fast interpolating transformations to threshold secret sharing schemes in cryptography.
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis