Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
On the arithmetic operations over finite fields of characteristic three with low complexity
Date
2014-03-15
Author
AKLEYLEK, SEDAT
Özbudak, Ferruh
Özel, Claire Susanna
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
163
views
0
downloads
Cite This
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 polynomial representation. We also investigate the matrix vector product method for the multiplication of the field elements represented by Hermite polynomials.
Subject Keywords
Finite field representation
,
Hermite polynomials
,
Modular multiplication
,
Matrix vector product method
URI
https://hdl.handle.net/11511/46286
Journal
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS
DOI
https://doi.org/10.1016/j.cam.2013.08.011
Collections
Department of Mathematics, Article
Suggestions
OpenMETU
Core
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...
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 complexity of Strassen-like matrix multiplications
Cenk, Murat (2017-05-01)
The Strassen algorithm for multiplying 2 x 2 matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension n yields a total arithmetic complexity of (7n(2.81) - 6n(2)) for n = 2(k). Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 2 x 2 matrices with seven multiplications is called a Strassen-like algorithm. Winograd also discovered an additively optimal Stras...
On the Orthogonality of q-Classical Polynomials of the Hahn Class
Alvarez-Nodarse, Renato; Adiguzel, Rezan Sevinik; Taşeli, Hasan (2012-01-01)
The central idea behind this review article is to discuss in a unified sense the orthogonality of all possible polynomial solutions of the q-hypergeometric difference equation on a q-linear lattice by means of a qualitative analysis of the q-Pearson equation. To be more specific, a geometrical approach has been used by taking into account every possible rational form of the polynomial coefficients in the q-Pearson equation, together with various relative positions of their zeros, to describe a desired q-wei...
On multiplication in finite fields
Cenk, Murat; Özbudak, Ferruh (2010-04-01)
We present a method for multiplication in finite fields which gives multiplication algorithms with improved or best known bilinear complexities for certain finite fields. Our method generalizes some earlier methods and combines them with the recently introduced complexity notion (M) over cap (q)(l), which denotes the minimum number of multiplications needed in F-q in order to obtain the coefficients of the product of two arbitrary l-term polynomials modulo x(l) in F-q[x]. We study our method for the finite ...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
S. AKLEYLEK, F. Özbudak, and C. S. Özel, “On the arithmetic operations over finite fields of characteristic three with low complexity,”
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS
, pp. 546–554, 2014, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/46286.