Obtaining more Karatsuba-like formulae over the binary field
作者： H. Fan , M. Gu , J. Sun , K.-Y. Lam
DOI: 10.1049/IET-IFS.2010.0114
关键词: Polynomial remainder theorem 、 Chinese remainder theorem 、 Algebra 、 Division algorithm 、 Karatsuba algorithm 、 Euclidean division 、 Mathematics 、 Method of successive substitution 、 Discrete mathematics 、 Short division 、 Remainder
摘要: The aim of this study is to find more Karatsuba-like formulae for a fixed set moduli polynomials in GF(2)[x]. To end, theoretical framework established. authors first generalise the division algorithm, and then present generalised definition remainder integer division. Finally, Chinese theorem used achieve their initial goal. As by-product division, rediscover Montgomery's N-residue systematic interpretation definitions multiplication addition operations.
core.ac.uk
aip.org
sci-hub.se 参考文章(14)
Tom M. Apostol, Introduction to analytic number theory ,(1976)
Joachim Von Zur Gathen, Jurgen Gerhard, Modern Computer Algebra ,(1999)
A. Karatsuba, Yu. Ofman, Multiplication of Multidigit Numbers on Automata Soviet physics. Doklady. ,vol. 7, pp. 595- 596 ,(1963)
Christof Paar, André Weimerskirch, Generalizations of the Karatsuba Algorithm for Efficient Implementations. IACR Cryptology ePrint Archive. ,vol. 2006, pp. 224- ,(2006)
Ivan Oseledets, Optimal Karatsuba-like formulae for certain bilinear forms in GF(2) Linear Algebra and its Applications. ,vol. 429, pp. 2052- 2066 ,(2008) , 10.1016/J.LAA.2008.06.004
Peter L. Montgomery, Modular multiplication without trial division Mathematics of Computation. ,vol. 44, pp. 519- 521 ,(1985) , 10.1090/S0025-5718-1985-0777282-X
A. Lempel, G. Seroussi, S. Winograd, On the complexity of multiplication in finite fields Theoretical Computer Science. ,vol. 22, pp. 285- 296 ,(1983) , 10.1016/0304-3975(83)90108-1
P.L. Montgomery, Five, six, and seven-term Karatsuba-like formulae IEEE Transactions on Computers. ,vol. 54, pp. 362- 369 ,(2005) , 10.1109/TC.2005.49
Paul Zimmermann, Richard Brent, Modern Computer Arithmetic ,(2010)
M. Cenk, F. Ozbudak, Improved Polynomial Multiplication Formulas over $IF₂$ Using Chinese Remainder Theorem IEEE Transactions on Computers. ,vol. 58, pp. 572- 576 ,(2009) , 10.1109/TC.2008.207