Efficient multiplication in double-struck F sign3ℓm, m ≥ 1 and 5 ≤ ℓ ≤ 18

Date

2008-06-14

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

227
views

0
downloads

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.

Subject Keywords

Chinese Remainder Theorem, Finite field multiplication, Pairing based cryptography

URI

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

DOI

https://doi.org/10.1007/978-3-540-68164-9_27

Conference Name

1st International Conference on Cryptology in Africa

Collections

Graduate School of Applied Mathematics, Conference / Seminar

Suggestions

OpenMETU
Core

Efficient multiplications in F(5)5n and F(7)7n Cenk, Murat; Özbudak, Ferruh (2011-08-15) 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...
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 ...
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 ...
Sparse polynomial multiplication for lattice-based cryptography with small complexity Akleylek, Sedat; Alkim, Erdem; Tok, Zaliha Yuce (2016-02-01) In this paper, we propose efficient modular polynomial multiplication methods with applications in lattice-based cryptography. We provide a sparse polynomial multiplication to be used in the quotient ring (Z/pZ)[x]/(x(n) + 1). Then, we modify this algorithm with sliding window method for sparse polynomial multiplication. Moreover, the proposed methods are independent of the choice of reduction polynomial. We also implement the proposed algorithms on the Core i5-3210M CPU platform and compare them with numbe...
Additive polynomials and primitive roots over finite fields Özbudak, Ferruh (2001-01-01) We prove existence of primitive roots with a prescribed nonzero image using the arithmetic of algebraic function fields for a class of polynomials over sufficiently large finite fields.

Citation Formats

M. Cenk and F. Özbudak, “Efficient multiplication in double-struck F sign3ℓm, m ≥ 1 and 5 ≤ ℓ ≤ 18,” presented at the 1st International Conference on Cryptology in Africa, Casablanca, MOROCCO, 2008, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/30779.