Fast Lagrange–Newton transformations

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.