FINITE FIELD MULTIPLICATION IN LAGRANGE REPRESENTATION USING FAST FOURRIER TRANSFORM

Christophe Negre

2006

Abstract

The multiplication in Fpn can be performed using a polynomial version of Montgomery multiplication (Montgomery, 1985). In (Bajard et al., 2003) Bajard et al. improved this method by using a Lagrange representation: the elements of Fpn are represented by their values at a fixed set of points. The costly operations in this new algorithm are the two changes of Lagrange representation which require 2r2 operations in Fp with n ≤ r ≤ 2⌈log2 (n)⌉ . In this paper we present a new method to perform the change of Lagrange representation. This method uses Fast Fourier Transform and has a cost equal to 3rlog2 (r) operations in Fp with r = 2⌈log2 (n)⌉ .

Paper Citation

in Harvard Style

Negre C. (2006). FINITE FIELD MULTIPLICATION IN LAGRANGE REPRESENTATION USING FAST FOURRIER TRANSFORM . In Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2006) ISBN 978-972-8865-63-4, pages 320-324. DOI: 10.5220/0002096503200324

in Bibtex Style

@conference{secrypt06,
author={Christophe Negre},
title={FINITE FIELD MULTIPLICATION IN LAGRANGE REPRESENTATION USING FAST FOURRIER TRANSFORM},
booktitle={Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2006)},
year={2006},
pages={320-324},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002096503200324},
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 - FINITE FIELD MULTIPLICATION IN LAGRANGE REPRESENTATION USING FAST FOURRIER TRANSFORM
SN - 978-972-8865-63-4
AU - Negre C.
PY - 2006
SP - 320
EP - 324
DO - 10.5220/0002096503200324