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

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.
1st International Conference on Cryptology in Africa

Suggestions

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.