Efficient multiplications in F(5)5n and F(7)7n

Date

2011-08-15

Author

Cenk, Murat
Özbudak, Ferruh

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

210
views

0
downloads

Efficient multiplications in finite fields of characteristics 5 and 7 are used for computing the Eta pairing over divisor class groups of the hyperelliptic curves Lee et al. (2008) [1]. In this paper, using the recent methods for multiplication in finite fields, the explicit formulas for multiplication in F(5)5n and F(7)7n are obtained with 10 multiplications in F(5)n for F(5)5n and 15 multiplications in F(7)n for F(7)7n improving the results in Cenk and Ozbudak (2008) [4], Cenk et al. (2009) [5], Lee et al. (2008) [11 and Montgomery (2005) [12]. The timing results of implementations of the Karatsuba type formulas and the proposed formula for multiplication in F(5)5.89 are given.

Subject Keywords

Finite field multiplication, Algebraic function fields, Pairing based cryptography

URI

https://hdl.handle.net/11511/32584

Journal

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

DOI

https://doi.org/10.1016/j.cam.2011.06.016

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

Efficient multiplication in double-struck F sign3ℓm, m ≥ 1 and 5 ≤ ℓ ≤ 18 Cenk, Murat; Özbudak, Ferruh (2008-06-14) 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.
On multiplication in finite fields Cenk, Murat; Özbudak, Ferruh (2010-04-01) 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 ...
Classification of function fields with class number three BİLHAN, Mehpare; Buyruk, Dilek; Özbudak, Ferruh (2015-11-01) We give the full list of all algebraic function fields over a finite field with class number three up to isomorphism. Our list consists of explicit equations of algebraic function fields which are mutually non-isomorphic over the full constant field.
Free storage basis conversion over extension field Harold, Ndangang Yampa; Akyıldız, Ersan; Department of Cryptography (2014) The representation of elements over finite fields play a great impact on the performance of finite field arithmetic. So if efficient representation of finite field elements exists and conversion between these representations is known, then it becomes easy to perform computation in a more efficient way. In this thesis, we shall provide a free storage basis conversion in the extension field F_(q^p) of F_q between Normal basis and Polynomial basis and vice versa. The particularity of this thesis is that, our t...
Efficient interleaved Montgomery modular multiplication for lattice-based cryptography AKLEYLEK, SEDAT; Tok, Zaliha Yuce (2014-01-01) In this paper, we give modified version of interleaved Montgomery modular multiplication method for lattice-based cryptography. With the proposed algorithms, we improve the multiplication complexity and embed the conversion operation into the algorithm with almost free cost. We implement the proposed methods for the quotient ring (Z/qZ)[x]/(x(n) - 1) and (Z/pZ)[x]/(x(n) + 1) on the GPU (NVIDIA Quadro 600) using the CUDA platform. NTRUEncrypt is accelerated approximately 35% on the GPU by using the proposed ...

Citation Formats

M. Cenk and F. Özbudak, “Efficient multiplications in F(5)5n and F(7)7n,” JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, pp. 177–183, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/32584.