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 条
  • [31] On the attraction of Newton’s method to critical lagrange multipliers
    E. I. Uskov
    Computational Mathematics and Mathematical Physics, 2013, 53 : 1099 - 1112
  • [32] On the numerical stability of Newton's formula for Lagrange interpolation
    de Camargo, Andre Pierro
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2020, 365
  • [33] Lagrange transformations and duality for corner and flag singularities
    Inna Scherbak
    Aviva Szpirglas
    Israel Journal of Mathematics, 1999, 111 : 77 - 92
  • [34] Bäcklund transformations for the rational Lagrange chain
    Fabio Musso
    Matteo Petrera
    Orlando Ragnisco
    Giovanni Satta
    Journal of Nonlinear Mathematical Physics, 2005, 12 (Suppl 2) : 240 - 252
  • [35] CANONICAL-TRANSFORMATIONS, LAGRANGE AND POISSON LEMMAS
    SCHRAPEL, HD
    ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND MECHANIK, 1980, 60 (08): : 309 - 316
  • [36] Lagrange transformations and duality for corner and flag singularities
    Scherbak, I
    Szpirglas, A
    ISRAEL JOURNAL OF MATHEMATICS, 1999, 111 (1) : 77 - 92
  • [37] Secret sharing a key in a distributed way, Lagrange vs Newton
    Voudouris, Anastassios
    Politis, Ilias
    Xenakis, Christos
    PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON AVAILABILITY, RELIABILITY AND SECURITY, ARES 2022, 2022,
  • [38] Measurement of subpixel displacement based on lagrange interpolation and Newton method
    Bai, FZ
    Han, F
    PROCEEDINGS OF THE THIRD INTERNATIONAL SYMPOSIUM ON INSTRUMENTATION SCIENCE AND TECHNOLOGY, VOL 2, 2004, : 43 - 47
  • [39] Elementary work, Newton law and Euler-Lagrange equations
    Udriste, Constantin
    Dogaru, Oltin
    Tevy, Ionel
    Bala, Dumitru
    BALKAN JOURNAL OF GEOMETRY AND ITS APPLICATIONS, 2010, 15 (02): : 100 - 107
  • [40] Complexity Comparison of Lagrange and Newton polynomial based revocation schemes
    Stavros, Dokouzyannis
    Iraklis, Spaliaras
    PROCEEDINGS OF THE 2ND EUROPEAN COMPUTING CONFERENCE: NEW ASPECTS ON COMPUTERS RESEACH, 2008, : 44 - +