Sparse multiplication for skew polynomials. (English) Zbl 07300071
Mantzaflaris, Angelos (ed.), Proceedings of the 45th international symposium on symbolic and algebraic computation, ISSAC ’20, Kalamata, Greece, July 20–23, 2020. New York, NY: Association for Computing Machinery (ACM). 194-201 (2020).
MSC:
| 68W30 | Symbolic computation and algebraic computation |
References:
| [1] | A. Arnold, M. Giesbrecht, and D. Roche. 2013. Faster sparse interpolation of straight-line programs. In International Workshop on Computer Algebra in Scientific Computing. Springer, 61-74. · Zbl 1411.68205 |
| [2] | A. Arnold and D. Roche. 2015. Output-sensitive algorithms for sumset and sparse polynomial multiplication. In ISSAC’15. ACM Press, 29-36. · Zbl 1346.68266 |
| [3] | D. Boucher, P. Gaborit, W. Geiselmann, O. Ruatta, and F. Ulmer. 2010. Key exchange and encryption schemes based on non-commutative skew polynomials. In International Workshop on Post-Quantum Cryptography. Springer, 126-141. · Zbl 1284.94055 |
| [4] | D. Boucher, W. Geiselmann, and F. Ulmer. 2007. Skew-cyclic codes. Applicable Algebra in Engineering, Communication and Computing 18, 4 (2007), 379-389. · Zbl 1159.94390 |
| [5] | D. Boucher and F. Ulmer. 2009. Coding with skew polynomial rings. Journal of Symbolic Computation 44, 12 (2009), 1644-1656. · Zbl 1174.94025 |
| [6] | X. Caruso and J. Le Borgne. 2017. Fast multiplication for skew polynomials. In ISSAC’17. ACM, 77-84. · Zbl 1457.68324 |
| [7] | D. Coppersmith and S. Winograd. 1990. Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 3 (1990), 251-280. · Zbl 0702.65046 |
| [8] | J.-M. Couveignes and R. Lercier. 2009. Elliptic periods for finite fields. Finite Fields Their Appl. 15, 1 (2009), 1-22. · Zbl 1216.11106 |
| [9] | E. Gabidulin. 1985. Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21, 1 (1985), 3-16. · Zbl 0585.94013 |
| [10] | F. Le Gall. 2014. Powers of tensors and fast matrix multiplication. In ISSAC’14. ACM Press, 296-303. · Zbl 1325.65061 |
| [11] | J. von zur Gathen and M. Giesbrecht. 1990. Constructing normal bases in finite fields. J. Symb. Comput 10 (1990), 547-570. · Zbl 0718.11065 |
| [12] | J. von zur Gathen and V. Shoup. 1992. Computing Frobenius maps and factoring polynomials. Computational Complexity 2, 3 (1992), 187-224. · Zbl 0778.11076 |
| [13] | W. Geiselmann and F. Ulmer. 2019. Skew Reed-Muller codes. Contemporary mathematics (2019), 107-116. · Zbl 1422.94037 |
| [14] | M. Giesbrecht. 1998. Factoring in skew-polynomial rings over finite fields. Journal of Symbolic Computation 26, 4 (1998), 463-486. · Zbl 0941.68160 |
| [15] | M. Giesbrecht, A. Jamshidpey, and É Schost. 2019. Quadratic-Time Algorithms for Normal Elements. In ISSAC’19. ACM Press, 179-186. · Zbl 1467.11124 |
| [16] | K. Girstmair. 1999. An algorithm for the construction of a normal basis. Journal of Number Theory 78, 1 (1999), 36-45. · Zbl 0954.11035 |
| [17] | D. Goss. 1996. Basic Structures of Function Field Arithmetic. Springer Berlin Heidelberg. · Zbl 0874.11004 |
| [18] | S. Johnson. 1974. Sparse polynomial arithmetic. ACM SIGSAM Bulletin 8, 3 (1974), 63-71. |
| [19] | E. Kaltofen and V. Shoup. 1998. Subquadratic-time factoring of polynomials over finite fields. Math. Comp. 67, 223 (1998), 1179-1197. · Zbl 0902.11053 |
| [20] | U. Martínez-Penas. 2019. Classification of multivariate skew polynomial rings over finite fields via affine transformations of variables. arXiv: 1908.06833 (2019). · Zbl 1469.11467 |
| [21] | U. Martínez-Penas and F. R. Kschischang. 2019. Evaluation and interpolation over multivariate skew polynomial rings. Journal of Algebra 525 (2019), 111-139. · Zbl 1443.16032 |
| [22] | M. Monagan and R. Pearce. 2009. Parallel Sparse Polynomial Multiplication Using Heaps. In ISSAC’09. 263-269. · Zbl 1237.68258 |
| [23] | M. Monagan and R. Pearce. 2011. Sparse Polynomial Pseudo Division Using a Heap. J. Symb. Comp. 46, 7 (2011), 807-822. · Zbl 1291.68435 |
| [24] | O. Ore. 1933. Theory of non-commutative polynomials. Annals of Mathematics (1933), 480-508. · Zbl 0007.15101 |
| [25] | S. Puchinger and A. Wachter-Zeh. 2016. Sub-quadratic decoding of Gabidulin codes. In 2016 IEEE International Symposium on Information Theory (ISIT). IEEE, 2554-2558. |
| [26] | S. Puchinger and A. Wachter-Zeh. 2018. Fast operations on linearized polynomials and their applications in coding theory. Journal of Symbolic Computation 89 (2018), 194-215. · Zbl 1398.12015 |
| [27] | F. Kschischang R. Koetter. 2008. Coding for errors and erasures in random network coding. IEEE Transactions on Information Theory 54, 8 (2008), 3579-3591. · Zbl 1318.94111 |
| [28] | D. Roche. 2018. What can (and can’t) we do with sparse polynomials?. In ISSAC’18. 25-30. · Zbl 1467.12003 |
| [29] | V. Shoup. 1994. Fast construction of irreducible polynomials over finite fields. Journal of Symbolic Computation 17, 5 (1994), 371-391. · Zbl 0815.11059 |
| [30] | J. van der Hoeven and G. Lecerf. 2012. On the Complexity of Multivariate Blockwise Polynomial Multiplication. In ISSAC’12. 211-218. · Zbl 1308.68199 |
| [31] | J. van der Hoeven and G. Lecerf. 2013. On the bit-complexity of sparse polynomial and series multiplication. J. Symbolic Computation 50 (2013), 227-254. · Zbl 1261.65017 |
| [32] | Y. Zhang. 2010. A secret sharing scheme via skew polynomials. In 2010 International Conference on Computational Science and Its Applications. IEEE, 33-38. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
