K?tter interpolation in skew polynomial rings

详细信息    查看全文

• 作者：Siyu Liu (1)
  Felice Manganiello (1)
  Frank R. Kschischang (1)
  
• 关键词：Skew polynomials ; K?tter interpolation ; Newton interpolation ; 11T71 ; 11T55
• 刊名：Designs, Codes and Cryptography
• 出版年：2014
• 出版时间：September 2014
• 年：2014
• 卷：72
• 期：3
• 页码：593-608
• 全文大小：
• 参考文献：1. Ore O.: Theory of non-commutative polynomials. Ann. Math. 34, 480-08 (1933).
  2. Cohn P.M.: Free Rings and Their Relations. Academic Press, London (1971).
  3. Jacobson N.: Finite Dimensional Division Algebras over Fields. Springer, Berlin (1996).
  4. Boucher D., Ulmer F.: Coding with skew polynomial rings. J. Symb. Comput. 44, 1644-656 (2009).
  5. Boucher D., Geiselmann W., Ulmer F.: Skew cyclic codes. Appl. Algebra Eng. Commun. Comput. 18, 379-89 (2007).
  6. Boucher D., Gaborit P., Geiselmann W., Ulmer, F.: Key exchange and encryption schemes based on non-commutative skew polynomials. Proc. PQCrypto. 6061, 126-41 (2010).
  7. Zhang Y.: A secret sharing scheme via skew polynomials. In: Proceedings of the 2010 International Conference on Computational Science and Its Applications, ICCSA -0, pp. 33-8. IEEE Computer Society, Washington, DC (2010).
  8. Sidorenko V., Jiang L., Bossert M.: Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes. IEEE Trans. Inform. Theory 57, 621-32 (2011).
  9. Gabidulin E.M.: Theory of codes with maximal rank distance. Probl. Inform. Trans. 21, 1-2 (1985).
  10. K?tter R., Kschischang F.: Coding for errors and erasures in random network coding. IEEE Trans. Inform. Theory 54, 3579-591 (2008).
  11. Lam T.Y., Leroy A.: Vandermonde and Wronskian matrices over division rings. J. Algebra 199, 306-36 (1988).
  12. Eric A.: Polynomial interpolation problem for skew polynomials. Appl. Anal. Discret. Math. 1, 403-14 (2007).
  13. Wang B., McEliece R.J., Watanabe K.: K?tter interpolation over free modules. In: Proceedings of 2005 Allerton Conferance on Communications Control and Computing, pp. 2197-206. SEP, Monticello (2005).
  14. Lidl R., Niederreiter H.: Introduction to Finite Fields and Their Applications. Cambridge University Press, Cambridge (1986).
  15. Lam T.Y.: A general theory of Vandermonde matrices. Expos. Math. 4, 193-15 (1986).
  16. Xie H., Yan Z., Suter B.: General linearized polynomial interpolation and its applications. In: 2011 International Symposium on Network Coding, pp. 1-. SNC, Beijing (2011).
  17. Cox D., Little J., O’Shea D.: Ideals, Varieties, and Algorithms. Springer, New York (1992).
  18. Berlekamp E.R.: Algebraic Coding Theory. McGraw-Hill, New York (1968).
  
• 作者单位：Siyu Liu (1)
  Felice Manganiello (1)
  Frank R. Kschischang (1)
  
  1. Department of Electrical and Computer Engineering, University of Toronto, 10 King’s College Road, Toronto, ON, M5S 3G4, Canada
  
• ISSN：1573-7586

文摘

Skew polynomials are a noncommutative generalization of ordinary polynomials that, in recent years, have found applications in coding theory and cryptography. Viewed as functions, skew polynomials have a well-defined evaluation map; however, little is known about skew-polynomial interpolation. In this work, we apply K?tter’s interpolation framework to free modules over skew polynomial rings. As a special case, we introduce a simple interpolation algorithm akin to Newton interpolation for ordinary polynomials.