Results on complexity of multiplication over finite fields

Download

index.pdf

Date

2009

Author

Cenk, Murat

Metadata

Show full item record

Item Usage Stats

152
views

54
downloads

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

M. Cenk, “Results on complexity of multiplication over finite fields,” Ph.D. - Doctoral Program, Middle East Technical University, 2009.