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.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/3/12610363/index.pdf |
| Date | 01 February 2009 |
| Creators | Cenk, Murat |
| Contributors | Ozbudak, Ferruh |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | Ph.D. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.0028 seconds