Multiplication in a Galois Ring

Date

2015-09-18

Author

AKLEYLEK, SEDAT
Özbudak, Ferruh

Metadata

Show full item record

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

Item Usage Stats

213
views

0
downloads

In this paper, we focus on the efficient multiplication in a Galois ring of the size 4(n), where n is a positive integer. We consider to adapt the finite field multiplication methods to the Galois ring multiplication. We give the polynomial multiplication in the Galois ring as a Toeplitz matrix-vector multiplication design with a modification used in finite fields of characteristic two. By this method, we reduce the multiplication complexity. Note that the proposed approach can be easily generalized to Galois rings of arbitrary characteristic. To the best of our knowledge, this is the first study to have a subquadratic space complexity to multiply two elements in the Galois rings.

Subject Keywords

Sequential multiplier, Polynomial multiplication, Toeplitz matrix-vector multiplication, Subquadratic space complexity multiplication, Galois ring

URI

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

Collections

Department of Mathematics, Conference / Seminar

Suggestions

OpenMETU
Core

Polynomial Multiplication over Binary Fields Using Charlier Polynomial Representation with Low Space Complexity AKLEYLEK, SEDAT; Cenk, Murat; Özbudak, Ferruh (2010-12-15) In this paper, we give a new way to represent certain finite fields GF(2(n)). This representation is based on Charlier polynomials. We show that multiplication in Charlier polynomial representation can be performed with subquadratic space complexity. One can obtain binomial or trinomial irreducible polynomials in Charlier polynomial representation which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. This repre...
On the arithmetic operations over finite fields of characteristic three with low complexity AKLEYLEK, SEDAT; Özbudak, Ferruh; Özel, Claire Susanna (2014-03-15) In this paper, the Hermite polynomial representation is adapted as a new way to represent certain finite fields of characteristic three. We give the multiplication method to multiply two elements of F-3n in the Hermite polynomial representation with subquadratic computational complexity by using a divide-and-conquer idea. We show that in some cases there is a set of irreducible binomials in the Hermite polynomial representation to obtain modular reduction with a lower addition complexity than the standard p...
Multiplication of polynomials modulo x(n) Cenk, Murat; Özbudak, Ferruh (2011-07-01) Let n, l be positive integers with l <= 2n - 1. Let R be an arbitrary nontrivial ring, not necessarily commutative and not necessarily having a multiplicative identity and R[x] be the polynomial ring over R. In this paper, we give improved upper bounds on the minimum number of multiplications needed to multiply two arbitrary polynomials of degree at most (n - 1) modulo x(n) over R. Moreover, we introduce a new complexity notion, the minimum number of multiplications needed to multiply two arbitrary polynomi...
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]/<x^n+-1> 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...
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 [2] 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

S. AKLEYLEK and F. Özbudak, “Multiplication in a Galois Ring,” 2015, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/53661.