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
Results on complexity of multiplication over finite fields
Download
index.pdf
Date
2009
Author
Cenk, Murat
Metadata
Show full item record
Item Usage Stats
177
views
62
downloads
Cite This
Let n and l be positive integers and f (x) be an irreducible polynomial over Fq such that ldeg( f (x)) < 2n - 1, where q is 2 or 3. We obtain an effective upper bound for the multiplication complexity of n-term polynomials modulo f (x)^l. This upper bound allows a better selection of the moduli when Chinese Remainder Theorem is used for polynomial multiplication over Fq. We give improved formulae to multiply polynomials of small degree over Fq. In particular we improve the best known multiplication complexities over Fq in the literature in some cases. Moreover, we present a method for multiplication in finite fields improving finite field multiplication complexity \muq(n) for certain values of q and n. We use local expansions, the lengths of which are further parameters that can be used to optimize the bounds on the bilinear complexity, instead of evaluation into residue class field. We show that we obtain improved bounds for multiplication in Fq^n for certain values of q and n where 2 <= n < =18 and q = 2, 3, 4.
Subject Keywords
Cryptography.
,
Mathematics.
URI
http://etd.lib.metu.edu.tr/upload/3/12610363/index.pdf
https://hdl.handle.net/11511/18402
Collections
Graduate School of Applied Mathematics, Thesis
Suggestions
OpenMETU
Core
Invariant subspaces for Banach space operators with an annular spectral set
Yavuz, Onur (2008-01-01)
Consider an annulus Omega = {z epsilon C : r(0) 0 such that parallel to p(T)parallel to <= K sup{vertical bar p(lambda)vertical bar : vertical bar lambda vertical bar <= 1} and parallel to p(r(0)T(-1))parallel to <= K sup{vertical bar p(lambda)vertical bar : vertical bar lambda vertical bar <= 1} for all polynomials p. Then there exists a nontrivial common invariant subspace for T* and T*(-1).
Improved Polynomial Multiplication Formulas over F-2 Using Chinese Remainder Theorem
Cenk, Murat; Özbudak, Ferruh (2009-04-01)
Let n and l be positive integers and f(x) be an irreducible polynomial over F-2 such that ldeg(f(x)) < 2n - 1. We obtain an effective upper bound for the multiplication complexity of n-term polynomials modulo f(x)(l). This upper bound allows a better selection of the moduli when the Chinese Remainder Theorem is used for polynomial multiplication over F-2. We give improved formulas to multiply polynomials of small degree over F-2. In particular, we improve the best known multiplication complexities over F-2 ...
An obstruction to finding algebraic models for smooth manifolds with prescribed algebraic submanifolds
CELIKTEN, A; Ozan, Yıldıray (2001-03-01)
Let N ⊆ M be a pair of closed smooth manifolds and L an algebraic model for the submanifold N. In this paper, we will give an obstruction to finding an algebraic model X of M so that the submanifold N corresponds in X to an algebraic subvariety isomorphic to L.
On homology of real algebraic varieties
Ozan, Yıldıray (American Mathematical Society (AMS), 2001-01-01)
Let R be a commutative ring with unity and X an R-oriented compact nonsingular real algebraic variety of dimension n. If i : X --> X-C is any nonsingular complexification of X, then the kernel, which we will denote by KHk(X, R), of the induced homomorphism i(*) : H-k(X, R) --> H-k(X-C, R) is independent of the complexification. In this work, we study KHk(X, R) and give some of its applications.
PERTURBATIONS OF NONASSOCIATIVE BANACH ALGEBRAS
Dosi, Anar (Rocky Mountain Mathematics Consortium, 2009-01-01)
In this note we prove that if either 21 is a Banach-Jordan algebra or a Banach-Lie algebra then all perturbations of the multiplication in 21 give algebras topologically isomorphic with 21 whenever certain small-dimension cohomology groups associated with 21 are vanishing.
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
M. Cenk, “Results on complexity of multiplication over finite fields,” Ph.D. - Doctoral Program, Middle East Technical University, 2009.