Browsing by Author "Ozbudak, Ferruh"

Now showing 1 - 4 of 4

Citation - WoS: 5
Citation - Scopus: 8
Efficient Multiplication in F3lm, M≥1 and 5≤l≤18
(Springer-verlag Berlin, 2008) Ozbudak, Ferruh; Cenk, Murat
Using a method based on Chinese Remainder Theorem for polynomial multiplication and suitable reductions, we obtain an efficient multiplication method for finite fields of characteristic 3. Large finite fields of characteristic 3 are important for pairing based cryptography [3]. For 5 <= l <= 18, we show that our method gives canonical multiplication formulae over F-3lm for any m >= 1 with the best multiplicative complexity improving the bounds in [6]. We give explicit formula in the case F-36.97.
Citation - WoS: 12
Citation - Scopus: 17
Improved Polynomial Multiplication Formulas Over F2 Using Chinese Remainder Theorem
(Ieee Computer Soc, 2009) Ozbudak, Ferruh; Cenk, Murat
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 in the literature in some cases.
Citation - WoS: 22
Citation - Scopus: 27
On Multiplication in Finite Fields
(Academic Press inc Elsevier Science, 2010) Ozbudak, Ferruh; Cenk, Murat
We present a method for multiplication in finite fields which gives multiplication algorithms with improved or best known bilinear complexities for certain finite fields. Our method generalizes some earlier methods and combines them with the recently introduced complexity notion (M) over cap (q)(l), which denotes the minimum number of multiplications needed in F-q in order to obtain the coefficients of the product of two arbitrary l-term polynomials modulo x(l) in F-q[x]. We study our method for the finite fields F(q)n, where 2 <= n <= 18 and q = 2, 3,4 and we improve or reach the currently best known bilinear complexities. We also give some applications in cryptography. (C) 2010 Published by Elsevier Inc.
Citation - WoS: 9
Citation - Scopus: 14
Polynomial Multiplication Over Finite Fields Using Field Extensions and Interpolation
(Ieee Computer Soc, 2009) Koc, Cetin Kaya; Ozbudak, Ferruh; Cenk, Murat; Koc, Etin Kaya; Zbudak, Ferruh O.
A method for polynomial multiplication over finite fields using field extensions and polynomial interpolation is introduced. The proposed method uses polynomial interpolation as Toom-Cook method together with field extensions. Furthermore, the proposed method can be used when Toom-Cook method cannot be applied directly. Explicit formulae improving the previous results in many cases are obtained.