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
25
views
13
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
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 ...
A note on the products ((m+1)(2)+1)((m+2)(2)+1) ... (n(2)+1) and ((m+1)(3)+1)((m+2)(3)+1) ... (n(3)+1)
Gurel, Erhan (2016-05-01)
We prove that for any positive integer m there exists a positive real number N-m such that whenever the integer n >= m neither the product P-m(n) = ((m + 1)(2) + 1) ((m + 2)(2) + 1) ... (n(2) + 1) nor the product Q(m)(n) = ((m + 1)(3) + 1)((m + 2)(3) + 1) ... (n(3) + 1) is a square.
Value sets of folding polynomials over finite fields
Küçüksakallı, Ömer (2019-01-01)
Let k be a positive integer that is relatively prime to the order of the Weyl group of a semisimple complex Lie algebra g. We find the cardinality of the value sets of the folding polynomials P-g(k)(x) is an element of Z[x] of arbitrary rank n >= 1, over finite fields. We achieve this by using a characterization of their fixed points in terms of exponential sums.
A New Algorithm for Residue Multiplication Modulo 2(521)-1
Ali, Shoukat; Cenk, Murat (2016-12-02)
We present a new algorithm for residue multiplication modulo the Mersenne prime p = 2(521) - 1 based on the Toeplitz matrix-vector product. For this modulus, our algorithm yields better result in terms of the total number of operations than the previously known best algorithm of Granger and Scott presented in Public Key Cryptography (PKC) 2015. We have implemented three versions of our algorithm to provide an extensive comparison - according to the best of our knowledge with respect to the well-known algori...
An alternative normal form for elliptic curve cryptography: Edwards curves
Muş, Köksal; Arslan, Sefa Feza; Department of Cryptography (2009)
A new normal form x2 + y2 = c2(1 + x2y2) of elliptic curves was introduced by M. Harold Edwards in 2007 over the field k having characteristic different than 2. This new form has very special and important properties such that addition operation is strongly unified and complete for properly chosen parameter c . In other words, doubling can be done by using the addition formula and any two points on the curve can be added by the addition formula without exception. D. Bernstein and T. Lange added one more par...
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.