Fast Lagrange-Newton transformations

被引:3
|
作者
Smarzewski, Ryszard [1 ]
Kapusta, Joanna [1 ]
机构
[1] John Paul II Catholic Univ Lublin, Dept Math & Comp Sci, PL-20708 Lublin, Poland
关键词
fast algorithms; Lagrange-Newton transformation; special configurations of knots; threshold secret sharing scheme; computational complexity;
D O I
10.1016/j.jco.2006.12.004
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this paper we present explicit vector formulae for the Lagrange-Newton transformation L: K-n -> K-n and its inverse L-1 with respect to interpolating knots x(i) = alpha x(i-1) + beta (i = 1, 2,.... n - 1 : x(0) = gamma). where alpha not equal 0, beta, gamma 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 (n log n)-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. (c) 2007 Elsevier Inc. All rights reserved.
引用
收藏
页码:336 / 345
页数:10
相关论文
共 50 条
  • [21] POLYNOMIAL INTERPOLATION - LAGRANGE VERSUS NEWTON
    WERNER, W
    MATHEMATICS OF COMPUTATION, 1984, 43 (167) : 205 - 217
  • [22] On the conditioning of the Newton formula for Lagrange interpolation
    Dinh Huu Lam
    Le Ngoc Cuong
    Phung Van Manh
    Nguyen Van Minh
    JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 2022, 505 (01)
  • [23] A Lagrange–Newton algorithm for sparse nonlinear programming
    Chen Zhao
    Naihua Xiu
    Houduo Qi
    Ziyan Luo
    Mathematical Programming, 2022, 195 : 903 - 928
  • [24] POTENTIAL-THEORY FROM NEWTON TO LAGRANGE
    CROSS, J
    HISTORIA MATHEMATICA, 1988, 15 (02) : 166 - 166
  • [25] On the accurate computation of the Newton form of the Lagrange interpolant
    Khiar, Y.
    Mainar, E.
    Royo-Amondarain, E.
    Rubio, B.
    NUMERICAL ALGORITHMS, 2025, 98 (03) : 1553 - 1573
  • [26] Backlund transformations for the rational Lagrange chain
    Musso, F
    Petrera, M
    Ragnisco, O
    Satta, G
    JOURNAL OF NONLINEAR MATHEMATICAL PHYSICS, 2005, 12 : 240 - 252
  • [27] Newton polyhedra and power transformations
    Bruno, AD
    MATHEMATICS AND COMPUTERS IN SIMULATION, 1998, 45 (5-6) : 429 - 443
  • [28] Optimal stability of the Lagrange formula and conditioning of the Newton formula
    Carnicer, J. M.
    Khiar, Y.
    Pena, J. M.
    JOURNAL OF APPROXIMATION THEORY, 2019, 238 : 52 - 66
  • [29] q-identities from Lagrange and Newton interpolation
    Fu, AM
    Lascoux, A
    ADVANCES IN APPLIED MATHEMATICS, 2003, 31 (03) : 527 - 531
  • [30] On the attraction of Newton's method to critical lagrange multipliers
    Uskov, E. I.
    COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS, 2013, 53 (08) : 1099 - 1112