On the Representation of Finite Fields

Download
index.pdf
2010
Akleylek, Sedat
Show full item record
130
views
30
downloads
The representation of field elements has a great impact on the performance of the finite field arithmetic. In this thesis, we give modified version of redundant representation which works for any finite fields of arbitrary characteristics to design arithmetic circuits with small complexity. Using our modified redundant representation, we improve many of the complexity values. We then propose new representations as an alternative way to represent finite fields of characteristic two by using Charlier and Hermite polynomials. We show that multiplication in these representations can be achieved with subquadratic space complexity. Charlier and Hermite representations enable us to find binomial, trinomial or quadranomial irreducible polynomials which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. These representations are very interesting for the NIST and SEC recommended binary fields GF(2^{283}) and GF(2^{571}) since there is no optimal normal basis (ONB) for the corresponding extensions. It is also shown that in some cases the proposed representations have better space complexity even if there exists an ONB for the corresponding extension.
Cryptography., Finite field.
http://etd.lib.metu.edu.tr/upload/12612727/index.pdf
https://hdl.handle.net/11511/20765
Graduate School of Applied Mathematics, Thesis

Suggestions

On the Attenuation of the Perfectly Matched Layer in Electromagnetic Scattering Problems with the Spectral Element Method
Mahariq, I.; Kuzuoğlu, Mustafa; Tarman, Işık Hakan (2014-09-01)
Although Spectral Element Method (SEM) has been applied in the modeling of boundary value problems of electromagnetics, its usage is not as common as the Finite Element or Finite Difference approaches in this area. It is well-known that the Perfectly Matched Layer (PML) approach is a mesh/grid truncation method in scattering or radiation applications where the spatial domain is unbounded. In this paper, the PML approach in the SEM context is investigated in two-dimensional, frequency-domain scattering probl...
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...
On the use of complex stretching coordinates in generalized finite difference method with applications in inhomogeneous visco-elasto dynamics
Korkut, Fuat; Mengi, Yalcin; Tokdemir, Turgut (2022-01-01)
In the study, in conjunction with perfectly matched layer (PML) analysis, an approach is proposed for the evaluation of complex derivatives directly in terms of complex stretching coordinates of points in PML. For doing this within the framework of generalized finite difference method (GFDM), a difference equation is formulated and presented, where both the function values and coordinates of data points might be complex. The use of the proposed approach is considered in the analysis of inhomogeneous visco-e...
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 ...
On the exact solution of the Schrodinger equation with a quartic anharmonicity
Taşeli, Hasan (1996-01-05)
A new version of solutions in the form of an exponentially weighted power series is constructed for the two-dimensional circularly symmetric quartic oscillators, which reflects successfully the desired properties of the exact wave function. The regular series part is shown to be the solution of a transformed equation. The transformed equation is applicable to the one-dimensional problem as well. Moreover, the exact closed-form eigenfunctions of the harmonic oscillator can be reproduced as a special case of ...
Citation Formats
S. Akleylek, “On the Representation of Finite Fields,” Ph.D. - Doctoral Program, Middle East Technical University, 2010.
METU IIS - Integrated Information Service open@metu.edu.tr