Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ore O.: Theory of non-commutative polynomials. Ann. Math. 34, 480–508 (1933).
Cohn P.M.: Free Rings and Their Relations. Academic Press, London (1971).
Jacobson N.: Finite Dimensional Division Algebras over Fields. Springer, Berlin (1996).
Boucher D., Ulmer F.: Coding with skew polynomial rings. J. Symb. Comput. 44, 1644–1656 (2009).
Boucher D., Geiselmann W., Ulmer F.: Skew cyclic codes. Appl. Algebra Eng. Commun. Comput. 18, 379–389 (2007).
Boucher D., Gaborit P., Geiselmann W., Ulmer, F.: Key exchange and encryption schemes based on non-commutative skew polynomials. Proc. PQCrypto. 6061, 126–141 (2010).
Zhang Y.: A secret sharing scheme via skew polynomials. In: Proceedings of the 2010 International Conference on Computational Science and Its Applications, ICCSA ’10, pp. 33–38. IEEE Computer Society, Washington, DC (2010).
Sidorenko V., Jiang L., Bossert M.: Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes. IEEE Trans. Inform. Theory 57, 621–632 (2011).
Gabidulin E.M.: Theory of codes with maximal rank distance. Probl. Inform. Trans. 21, 1–12 (1985).
Kötter R., Kschischang F.: Coding for errors and erasures in random network coding. IEEE Trans. Inform. Theory 54, 3579–3591 (2008).
Lam T.Y., Leroy A.: Vandermonde and Wronskian matrices over division rings. J. Algebra 199, 306–336 (1988).
Eric A.: Polynomial interpolation problem for skew polynomials. Appl. Anal. Discret. Math. 1, 403–414 (2007).
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–2206. SEP, Monticello (2005).
Lidl R., Niederreiter H.: Introduction to Finite Fields and Their Applications. Cambridge University Press, Cambridge (1986).
Lam T.Y.: A general theory of Vandermonde matrices. Expos. Math. 4, 193–215 (1986).
Xie H., Yan Z., Suter B.: General linearized polynomial interpolation and its applications. In: 2011 International Symposium on Network Coding, pp. 1–4. SNC, Beijing (2011).
Cox D., Little J., O’Shea D.: Ideals, Varieties, and Algorithms. Springer, New York (1992).
Berlekamp E.R.: Algebraic Coding Theory. McGraw-Hill, New York (1968).
Acknowledgments
The second author was supported by the Swiss National Science Foundation under Grant No. 135934.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by P. Charpin.
Rights and permissions
About this article
Cite this article
Liu, S., Manganiello, F. & Kschischang, F.R. Kötter interpolation in skew polynomial rings. Des. Codes Cryptogr. 72, 593–608 (2014). https://doi.org/10.1007/s10623-012-9784-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-012-9784-1