New Efficient Algorithms for Multiplication Over Fields of Characteristic Three

Date

2018-03-01

Author

Cenk, Murat
Hasan, M. Anwar

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

199
views

0
downloads

In this paper, we first present an enhancement of the well-known Karatsuba 2-way and 3-way algorithms for characteristic three fields, denoted by where nae1. We then derive a 3-way polynomial multiplication algorithm with five 1/3 sized multiplications that use interpolation in . Following the computation of the arithmetic and delay complexity of the proposed algorithm, we provide the results of our hardware implementation of polynomial multiplications over and . The final proposal is a new 3-way polynomial multiplication algorithm over that uses three polynomial multiplications of 1/3 of the original size over and one polynomial multiplication of 1/3 of the original size over . We show that this algorithm represents about 15% reduction of the complexity over previous algorithms for the polynomial multiplications whose sizes are of practical interest.

Subject Keywords

Polynomial Multiplication, Elliptic curves, Characteristic three fields

URI

https://hdl.handle.net/11511/30457

Journal

JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY

DOI

https://doi.org/10.1007/s11265-017-1234-x

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

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...
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.
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...
A New Representation of Elements of Binary Fields with Subquadratic Space Complexity Multiplication of Polynomials Özbudak, Ferruh; Cenk, Murat (2013-10-01) In this paper, Hermite polynomial representation is proposed as an alternative way to represent finite fields of characteristic two. We show that multiplication in Hermite polynomial representation can be achieved with subquadratic space complexity. This representation enables us to find binomial or trinomial irreducible polynomials which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. We then show that the pro...
Some new results on binary polynomial multiplication Cenk, Murat (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 ...

Citation Formats

M. Cenk and M. A. Hasan, “New Efficient Algorithms for Multiplication Over Fields of Characteristic Three,” JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY, pp. 285–294, 2018, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/30457.