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

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
M. Cenk, “Results on complexity of multiplication over finite fields,” Ph.D. - Doctoral Program, Middle East Technical University, 2009.