Article ID Journal Published Year Pages File Type
4609043 Journal of Complexity 2007 10 Pages PDF
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