ANALYSIS AND IMPLEMENTATION OF BINARY POLYNOMIAL MULTIPLICATION

Download

ANALYSIS_AND_IMPLEMENTATION_OF_BINARY_POLYNOMIAL_MULTIPLICATION-2.pdf

Date

2021-9-09

Author

OLUDO, Mary Achieng

Metadata

Show full item record

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

Item Usage Stats

417
views

407
downloads

N. Koblitz and V. Miller originally proposed the concept of elliptic curve cryptography in 1985. It is fast gaining popularity in public key cryptosystems as it boasts of an advantage over current public key cryptosystems, that is, the requirement of the key size be smaller and still maintain the same level of security. It takes advantage of elliptic curves’ mathematical properties in finite fields. Elliptic curve cryptographic systems perform operations on points on elliptic curves. Elliptic curves can be represented over prime fields and can also be represented over binary fields. In the binary field representation, the elements of these finite fields are binary polynomials. Polynomial multiplication is a key operation in binary field elliptic curve cryptographic implementation and hence an area of interest in cryptography. In this thesis,we analyse some polynomial multiplication algorithms over binary fields. For 2-way algorithms we investigate schoolbook, Karatsuba and refined Karatsuba and for 3-way algorithms we investigate schoolbook, Karatsuba and CNH 3-way split algorithms. We define a 64-bit by 64-bit multiplication as the smallest unit of computation for a polynomial multiplication which can also be improved by the sliding window method. We have observed that an optimal size of eight for the window size is attained with a time memory trade off.

Subject Keywords

Elliptic Curves, Karatsuba, CNH 3-Way Split

URI

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

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

Elliptic curves and use of their endomorphism rings in cryptography Sülçe, Ali Mert; Akyıldız, Ersan; Department of Cryptography (2019) Although elliptic curves have been studied for hundreds of years, the inception of elliptic curve cryptography is 1985 by Koblitz’s and Miller’s independent proposals that is based on the discrete logarithm problem on an elliptic curve defined over a finite field. After that date, there are a lot of advances and studies in elliptic curve cryptography(ECC) which provide high security with relatively small block sizes and high speed compared to the other public key cryptosystems. For instance, 160-bit ellipti...
Elliptic curve pairing-based cryptography Kırlar, Barış Bülent; Akyıldız, Ersan; Department of Cryptography (2010) In this thesis, we explore the pairing-based cryptography on elliptic curves from the theoretical and implementation point of view. In this respect, we first study so-called pairing-friendly elliptic curves used in pairing-based cryptography. We classify these curves according to their construction methods and study them in details. Inspired of the work of Koblitz and Menezes, we study the elliptic curves in the form $y^{2}=x^{3}-c$ over the prime field $\F_{q}$ and compute explicitly the number of points $...
Strictly singular operators and isomorphisms of Cartesian products of power series spaces Djakov, PB; Onal, S; Terzioglu, T; Yurdakul, Murat Hayrettin (1998-01-02) V. P. Zahariuta, in 1973, used the theory of Fredholm operators to develop a method to classify Cartesian products of locally convex spaces. In this work we modify his method to study the isomorphic classification of Cartesian products of the kind E-0(p)(a) x E-infinity(q) (b) where 1 less than or equal to p, q < infinity, p not equal q, a = (a(n))(n=1)(infinity) and b = (b(n))(n=1)(infinity) are sequences of positive numbers and E-0(p)(a), E(infinity)q(b) are respectively l(p)-finite and l(q)-infinite type...
Efficient subquadratic space complexity binary polynomial multipliers based on block recombination Cenk, Murat; Negre, Christophe (2014-09-01) Some applications like cryptography involve a large number of multiplications of binary polynomial. In this paper we consider two, three and four-way methods for parallel implementation of binary polynomial multiplication. We propose optimized three and four-way split formulas which reduce the space and time complexity of the best known methods. Moreover, we present a block recombination method which provides some further reduction in the space complexity of the considered two, three and four-way split mult...
MUTATION CLASSES OF SKEW-SYMMETRIZABLE 3 x 3 MATRICES Seven, Ahmet İrfan (2013-05-01) Mutation of skew-symmetrizable matrices is a fundamental operation that first arose in Fomin-Zelevinsky's theory of cluster algebras; it also appears naturally in many different areas of mathematics. In this paper, we study mutation classes of skew-symmetrizable 3 x 3 matrices and associated graphs. We determine representatives for these classes using a natural minimality condition, generalizing and strengthening results of Beineke-BrustleHille and Felikson-Shapiro-Tumarkin. Furthermore, we obtain a new num...

Citation Formats

M. A. OLUDO, “ANALYSIS AND IMPLEMENTATION OF BINARY POLYNOMIAL MULTIPLICATION,” M.S. - Master of Science, Middle East Technical University, 2021.