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).

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