AN EFFICIENT MULTIPLICATION ALGORITHM USING BINOMIAL RESIDUE REPRESENTATION

Yin Li, Christophe Negre

2008

Abstract

In this paper, we propose an extension of the algorithm proposed by Bajard, Imbert and Negre in (Bajar et al., 2006), refered as BIN algorithm. We use binomial residue representation of field elements instead of the Lagrange representation of (Bajar et al., 2006). Specifically, every elements in Fpk is represented by a set of residue modulo fixed binomials. We propose two versions of our algorithm, one in general form with a sub-quadratic complexity equal to O(k1.5 ) operations in Fp . The second one is optimized with the use of FFT. In this case the cost is O(k log(k)) operations in Fp . For fields GF ( pk ) suitable for elliptic curve cryptography our algorithm roughly improves the time delay of (Bajar et al., 2006) by 45%.

Paper Citation

in Harvard Style

Li Y. and Negre C. (2008). AN EFFICIENT MULTIPLICATION ALGORITHM USING BINOMIAL RESIDUE REPRESENTATION . In Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2008) ISBN 978-989-8111-59-3, pages 319-324. DOI: 10.5220/0001924503190324

in Bibtex Style

@conference{secrypt08,
author={Yin Li and Christophe Negre},
title={AN EFFICIENT MULTIPLICATION ALGORITHM USING BINOMIAL RESIDUE REPRESENTATION},
booktitle={Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2008)},
year={2008},
pages={319-324},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001924503190324},
isbn={978-989-8111-59-3},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2008)
TI - AN EFFICIENT MULTIPLICATION ALGORITHM USING BINOMIAL RESIDUE REPRESENTATION
SN - 978-989-8111-59-3
AU - Li Y.
AU - Negre C.
PY - 2008
SP - 319
EP - 324
DO - 10.5220/0001924503190324