Results on complexity of multiplication over finite fields

Download
2009
Cenk, Murat
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.

Suggestions

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.