Fast interpolating algorithms in cryptography

Abstract

We present two fast polynomial interpolating algorithms with knots generated in a field K by the recurrent formula of the form xf = axj_l + ft (z = 1,2,..,« -1; x0 = . The running time of them is C(n) + 0(n) base operations from K, where C(n) = 0(n\og2 n) denotes the time needed to compute the wrapped convolution in K. Moreover, we give an application of these algorithms to threshold secret sharing schemes in cryptography.