On multiplication in finite fields

Date

2010-04-01

Author

Cenk, Murat
Ö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

266
views

0
downloads

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 fields F(q)n, where 2 <= n <= 18 and q = 2, 3,4 and we improve or reach the currently best known bilinear complexities. We also give some applications in cryptography. (C) 2010 Published by Elsevier Inc.

Subject Keywords

Finite fields, Algebraic function fields, Bilinear complexity

URI

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

Journal

JOURNAL OF COMPLEXITY

DOI

https://doi.org/10.1016/j.jco.2009.11.002

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

Classification of function fields with class number three BİLHAN, Mehpare; Buyruk, Dilek; Özbudak, Ferruh (2015-11-01) We give the full list of all algebraic function fields over a finite field with class number three up to isomorphism. Our list consists of explicit equations of algebraic function fields which are mutually non-isomorphic over the full constant field.
Additive polynomials and primitive roots over finite fields Özbudak, Ferruh (2001-01-01) We prove existence of primitive roots with a prescribed nonzero image using the arithmetic of algebraic function fields for a class of polynomials over sufficiently large finite fields.
Efficient multiplications in F(5)5n and F(7)7n Cenk, Murat; Özbudak, Ferruh (2011-08-15) Efficient multiplications in finite fields of characteristics 5 and 7 are used for computing the Eta pairing over divisor class groups of the hyperelliptic curves Lee et al. (2008) [1]. In this paper, using the recent methods for multiplication in finite fields, the explicit formulas for multiplication in F(5)5n and F(7)7n are obtained with 10 multiplications in F(5)n for F(5)5n and 15 multiplications in F(7)n for F(7)7n improving the results in Cenk and Ozbudak (2008) [4], Cenk et al. (2009) [5], Lee et al...
Free storage basis conversion over extension field Harold, Ndangang Yampa; Akyıldız, Ersan; Department of Cryptography (2014) The representation of elements over finite fields play a great impact on the performance of finite field arithmetic. So if efficient representation of finite field elements exists and conversion between these representations is known, then it becomes easy to perform computation in a more efficient way. In this thesis, we shall provide a free storage basis conversion in the extension field F_(q^p) of F_q between Normal basis and Polynomial basis and vice versa. The particularity of this thesis is that, our t...
Character sums of quadratic forms over finite fields and the number of rational points for some classes of artin-schreier type curves Coşgun, Ayhan; Doğanaksoy, Ali; Department of Mathematics (2017) Exponential sums of quadratic forms over finite fields have many applications to various areas such as coding theory and cryptography. As an example to these applications, there is an organic connection between exponential sums of quadratic forms and the number of rational points of algebraic curves defined over finite fields. This connection is central in the application of algebraic geometry to coding theory and cryptography. In this thesis, different facts and techniques of theory of finite fields are co...

Citation Formats

M. Cenk and F. Özbudak, “On multiplication in finite fields,” JOURNAL OF COMPLEXITY, pp. 172–186, 2010, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/32570.