PARALLEL MULTIPLICATION IN F2n USING CONDENSED MATRIX REPRESENTATION

Christophe Negre

2006

Abstract

In this paper we explore a matrix representation of binary fields F2n defined by an irreducible trinomial P = X n + X k + 1. We obtain a multiplier with time complexity of TA + (⌈log 2(n)⌉)TX and space 2 complexity of (2n − 1)n AND and (2n − 1)(n − 1) XOR . This multiplier reaches the lower bound on time complexity. Until now this was possible only for binary field defined by AOP (Silverman, 1999), which are quite few. The interest of this multiplier remains theoretical since the size of the architecture is roughly two times bigger than usual polynomial basis multiplier (Mastrovito, 1991; Koc and Sunar, 1999).

References

  1. Berlekamp, E. (1982). Bit-serial Reed-Solomon encoder. IEEE Trans. Information Theory, IT-28:869-874.
  2. Chang, K.-Y., Hong, D., and Cho, H.-S. (2005). Low complexity bit-parallel multiplier for GF(2m) defined by all-one polynomials using redundant representation. IEEE Trans. Comput., 54(12):1628-1630.
  3. Koc, C. and Sunar, B. (1999). Mastrovito Multiplier for All Trinomials. IEEE Transaction on Computers, 48(5):522-52.
  4. Koc, C. and Sunar, B. (2001). An Efficient Optimal Normal Basis Type II Multiplier. IEEE Trans. on Computers, 50:83-87.
  5. Lidl, R. and Niederreiter, H. (1986). Introduction to Finite Fields and Their Applications. Cambridge Univ Press.
  6. Mastrovito, E. (1991). VLSI architectures for computations in Galois fields. PhD thesis, Dep.Elec.Eng.,Linkoping Univ.
  7. Miller, V. (1985). Uses of elliptic curves in cryptography. Advances in Cryptology, proceeding's of CRYPTO'85, Lecture Note in Computer Science 218.
  8. Silverman, J. H. (1999). Fast Multiplication in Finite Fields GF(2n). In Crytographic Hardware and Embedded Systems - CHES'99, volume 1717 of LNCS, pages 122-134.
  9. Wu, H. and Hasan, M. (1998). Low-Complexity Multipliers Bit-Parallel for a Class of Finite Fields. IEEE Trans. Computers, 47:883-887.
Download


Paper Citation


in Harvard Style

Negre C. (2006). PARALLEL MULTIPLICATION IN F2n USING CONDENSED MATRIX REPRESENTATION . In Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2006) ISBN 978-972-8865-63-4, pages 254-259. DOI: 10.5220/0002096402540259


in Bibtex Style

@conference{secrypt06,
author={Christophe Negre},
title={PARALLEL MULTIPLICATION IN F2n USING CONDENSED MATRIX REPRESENTATION},
booktitle={Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2006)},
year={2006},
pages={254-259},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002096402540259},
isbn={978-972-8865-63-4},
}


in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2006)
TI - PARALLEL MULTIPLICATION IN F2n USING CONDENSED MATRIX REPRESENTATION
SN - 978-972-8865-63-4
AU - Negre C.
PY - 2006
SP - 254
EP - 259
DO - 10.5220/0002096402540259