Fast software multiplication in $Bbb{F} _2 [x]$ for embedded processors
Fast software multiplication in $Bbb{F} _2 [x]$ for embedded processors
We present a novel method for fast multiplication of polynomials over $Bbb{F} _2 $ which can be implemented efficiently in embedded software. Fast polynomial multiplication methods are needed for the efficient implementation of some cryptographic and coding applications. The proposed method follows a strategy to reduce the memory accesses for input data and intermediate values during computation. This strategy speeds up the binary polynomial multiplication significantly on typical embedded processors with limited memory bandwidth. These multiplications are usually performed by the comb method or the Karatsuba-based methods in embedded software. The proposed method has speed and memory advantages over these methods on embedded platforms for the polynomial degrees usually encountered in practical cryptosystems. We perform a detailed complexity analysis of the proposed method and complexity comparisons with the other methods. Finally, we present the running times of the proposed method and its alternatives on ARM7TDMI processor.
___
- [1] J. von zur Gathen and J. Gerhard, “Arithmetic and factorization of polynomial over F2 ” (extended abstract), In ISSAC, pages 1–9, 1996.
- [2] J. von zur Gathen and J. Gerhard, “Polynomial factorization over F2 ”, Mathematics of Computation, 71(240):1677– 1698, 2002.
- [3] H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen, and F. Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Discrete Mathematics and its Applications, Chapman & Hall/CRC, 2005.
- [4] D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag New York, Inc., 2004.
- [5] A. Weimerskirch, D. Stebila, and S. C. Shantz, “Generic GF(2) arithmetic in software and its application to ECC”, In ACISP, pages 79–92, 2003.
- [6] J. Lopez and R. Dahab, “High-speed software multiplication in F2m ”, In INDOCRYPT, pages 203–212, 2000.
- [7] A. A. Karatsuba and Y. Ofman, “Multiplication of multidigit numbers on automata”, Soviet Physics-Doklady (English translation), 7(7):595–596, 1963.
- [8] D. E. Knuth, Seminumerical Algorithms, volume 2 of The Art of Computer Programming, Addison-Wesley, Reading, MA, 3rd edition, 1997.
- [9] P. L. Montgomery, “Five, six, and seven-term Karatsuba-like formulae”, IEEE Transactions on Computers, 54(3):362–369, 2005.
- [10] R. P. Brent, P. Gaudry, E. Thome, and P. Zimmermann, “Faster multiplication in GF(2)[x]”, In ANTS, pages 153–166, 2008.
- [11] S. Bartolini, I. Branovic, R. Giorgi, and E. Martinelli, “Effects of instruction-set extensions on an embedded processor: A case study on elliptic-curve cryptography over GF(2m)”, IEEE Transactions on Computers, 57(5):672– 685, 2008.
- ISSN: 1300-0632
- Yayın Aralığı: Yılda 6 Sayı
- Yayıncı: TÜBİTAK