Abstract
In this paper, we first present an enhancement of the well-known Karatsuba 2-way and 3-way algorithms for characteristic three fields, denoted by \(\mathbb {F}_{3^{n}}\) where n≥1. We then derive a 3-way polynomial multiplication algorithm with five 1/3 sized multiplications that use interpolation in \(\mathbb {F}_{9}\). Following the computation of the arithmetic and delay complexity of the proposed algorithm, we provide the results of our hardware implementation of polynomial multiplications over \(\mathbb {F}_{3}\) and \(\mathbb {F}_{9}\). The final proposal is a new 3-way polynomial multiplication algorithm over \(\mathbb {F}_{3}\) that uses three polynomial multiplications of 1/3 of the original size over \(\mathbb {F}_{3}\) and one polynomial multiplication of 1/3 of the original size over \(\mathbb {F}_{9}\). We show that this algorithm represents about 15% reduction of the complexity over previous algorithms for the polynomial multiplications whose sizes are of practical interest.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahmadi, O., Hankerson, D., & Menezes, A. (2007). Formulas for cube roots in F\(_{3^{\mathrm {m}}}\). Discrete Applied Mathematics, 155(3).
Ahmadi, O., Hankerson, D., & Menezes, A. (2007). Software implementation of arithmetic in F\(_{3^{\mathrm {m}}}\). In WAIFI (pp. 85–102).
Barbulescu, R., Detrey, J., Estibals, N., & Zimmermann, P. (2012). Finding optimal formulae for bilinear maps. In WAIFI (pp. 168–186).
Bernstein, D.J. (2009). Batch binary Edwards. In Advances in cryptology - CRYPTO 2009, volume 5677 of LNCS (pp. 317–336).
Cenk, M., Koç, Ç. K., & Özbudak, F. (2009). Polynomial multiplication over finite fields using field extensions and interpolation. In IEEE symposium on computer arithmetic (pp. 84–91).
Cenk, M., Hasan, M.A., & Negre, C. (2014). Efficient subquadratic space complexity binary polynomial multipliers based on block recombination. IEEE Transactions on Computers, 63(9), 2273–2287.
Cenk, M., Negre, C., & Hasan, M. A. (2011). Improved three-way split formulas for binary polynomial multiplication. In Selected areas in cryptography (pp. 384–398).
Cenk, M., Negre, C., & Anwar Hasan, M. (2013). Improved three-way split formulas for binary polynomial and toeplitz matrix vector products. IEEE Transactions on Computers, 62(7), 1345–1361.
Cenk, M., & Özbudak, F. (2008). Efficient multiplication in \(\mathbb {F}_{3^{\ell m}}\), m≥1 and 5≤ℓ≤18. In AFRICACRYPT (pp. 406–414).
Fan, H., & Hasan, M. A. (2007). A new approach to subquadratic space complexity parallel multipliers for extended binary fields. IEEE Transactions on Computers, 56(2), 224–233.
Farashahi, R. R., Wu, H., & Zhao, C. (2013). Efficient arithmetic on elliptic curves over fields of characteristic three. In Selected areas in cryptography (pp. 135–148).
Von Zur Gathen, J., & Gerhard, J. (2013). Modern computer algebra, 3rd edn. Cambridge: Cambridge University Press.
Gorla, E., Puttmann, C., & Shokrollahi, J. (2007). Explicit formulas for efficient multiplication in \(F_{3^{6m}}\). In Selected areas in cryptography (pp. 173–183).
Hisil, H., Carter, G., & Dawson, E. (2007). New formulae for efficient elliptic curve arithmetic. In Progress in cryptology–INDOCRYPT 2007 (pp. 138–151).
Karatsuba, A. A., & Ofman, Y. (1963). Multiplication of multidigit numbers on automata. Soviet Physics Doklady, 7(2), 595–596.
Kim, K. H., Choe, J. S., & Kim, S. I. (2007). New fast algorithms for arithmetic on elliptic curves over finite fields of characteristic three. Cryptology ePrint Archive, Technical Report 2007/179.
Koblitz, N. (1998). An elliptic curve implementation of the finite field digital signature algorithm. In Advances in cryptology–CRYPTO’98 (pp. 327–337). Springer.
Montgomery, P. L. (2005). Five, six, and seven-term karatsuba-like formulae. IEEE Transactions on Computers, 54(3), 362–369.
Negre, C. (2005). Scalar multiplication on elliptic curves defined over fields of small odd characteristic. In Progress in cryptology–INDOCRYPT 2005 (pp. 389–402). Springer.
Page, D., & Smart, N. P. (2003). Hardware implementation of finite fields of characteristic three. In Cryptographic hardware and embedded systems-CHES 2002 (pp. 529–539). Springer.
Smart, N. P., & Westwood, E. J. (2003). Point multiplication on ordinary elliptic curves over fields of characteristic three. Applicable Algebra in Engineering, Communication and Computing, 13(6), 485–497.
Winograd, S. (1980). Arithmetic complexity of computations. Society For Industrial & Applied Mathematics, U.S.
Zhou, G., & Michalik, H. (2010). Comments on a new architecture for a parallel finite field multiplier with low complexity based on composite field. IEEE Transactions on Computers, 59(7), 1007–1008.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
A high level block diagram of our circuits for the multiplication algorithm of A19 is presented in Fig. 2. A and B are two degree (n−1) polynomials over \(\mathbb {F}_{3}\). They are split into three parts as A(X) = A 0 + A 1 X n/3 + A 2 X 2n/3 and B(X) = B 0 + B 1 X n/3 + B 2 X 2n/3 where A i and B i are polynomials of degree less than n/3. For the details of the algorithm, we refer the reader to Section 4.
A high level block diagram of A19.
Rights and permissions
About this article
Cite this article
Cenk, M., Zadeh, F.H. & Hasan, M.A. New Efficient Algorithms for Multiplication Over Fields of Characteristic Three. J Sign Process Syst 90, 285–294 (2018). https://doi.org/10.1007/s11265-017-1234-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11265-017-1234-x