# Some new results on binary polynomial multiplication

2015-11-01
This paper presents several methods for reducing the number of bit operations for multiplication of polynomials over the binary field. First, a modified Bernstein's 3-way algorithm is introduced, followed by a new 5-way algorithm. Next, a new 3-way algorithm that improves asymptotic arithmetic complexity compared to Bernstein's 3-way algorithm is introduced. This new algorithm uses three multiplications of one-third size polynomials over the binary field and one multiplication of one-third size polynomials over the finite field with four elements. Unlike Bernstein's algorithm, which has a linear delay complexity with respect to input size, the delay complexity of the new algorithm is logarithmic. The number of bit operations for the multiplication of polynomials over the finite field with four elements is also computed. Finally, all these new results are combined to obtain improved complexities.
JOURNAL OF CRYPTOGRAPHIC ENGINEERING

# Suggestions

 Improved three-way split formulas for binary polynomial multiplication Cenk, Murat; Hasan, M. Anwar (2011-08-12) In this paper we deal with 3-way split formulas for binary field multiplication with five recursive multiplications of smaller sizes. We first recall the formula proposed by Bernstein at CRYPTO 2009 and derive the complexity of a parallel multiplier based on this formula. We then propose a new set of 3-way split formulas with five recursive multiplications based on field extension. We evaluate their complexities and provide a comparison.
 A New Algorithm for Residue Multiplication Modulo 2(521)-1 Ali, Shoukat; Cenk, Murat (2016-12-02) We present a new algorithm for residue multiplication modulo the Mersenne prime p = 2(521) - 1 based on the Toeplitz matrix-vector product. For this modulus, our algorithm yields better result in terms of the total number of operations than the previously known best algorithm of Granger and Scott presented in Public Key Cryptography (PKC) 2015. We have implemented three versions of our algorithm to provide an extensive comparison - according to the best of our knowledge with respect to the well-known algori...
 HYBRID ANALYSIS OF TMVP FOR MODULAR POLYNOMIAL MULTIPLICATION IN CRYPTOGRAPHY Efe, Giray; Cenk, Murat; Department of Cryptography (2022-3-07) Polynomial multiplication on the quotient ring Z[x]/ is one of the most fundamental, general-purpose operations frequently used in cryptographic algorithms. Therefore, a possible improvement over a multiplication algorithm directly affects the performance of algorithms used in a cryptographic application. Well-known multiplication algorithms such as Schoolbook, Karatsuba, and Toom-Cook are dominant choices against NTT in small and ordinary input sizes. On the other hand, how these approaches are imp...
 NEW EFFICIENT CHARACTERISTIC THREE POLYNOMIAL MULTIPLICATION ALGORITHMS AND THEIR APPLICATIONS TO NTRU PRIME Yeniaras, Esra; Cenk, Murat; Department of Cryptography (2022-1-21) Some of the post-quantum cryptographic protocols require polynomial multiplication in characteristic three fields, thus the efficiency of such multiplication algorithms gain more importance recently. In this thesis, we propose four new polynomial multiplication algorithms in characteristic three fields and we show that they are more efficient than the current state-of-the-art methods. We first analyze the well-known algorithms such as the schoolbook method, Karatsuba 2-way and 3-way split methods, Bernstein...
 Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication Taskin, Halil Kemal; Cenk, Murat (2018-01-24) This paper proposes a new multiplication algorithm over F-2(255)-19 where the de-facto standard Curve25519  algorithm is based on. Our algorithm for the underlying finite field multiplication exploits the Toeplitz matrix-vector multiplication and achieves salient results. We have used a new radix representation that is infeasible when used with schoolbook multiplication techniques but has notable advantages when used with Toeplitz matrix-vector multiplication methods. We present the new algorithm and dis...
Citation Formats
M. Cenk, “Some new results on binary polynomial multiplication,” JOURNAL OF CRYPTOGRAPHIC ENGINEERING, pp. 289–303, 2015, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/30596. 