| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Redundant Representation of GF(q^n) for Designing Arithmetic Circuits
July 2003 (vol. 52 no. 7)
pp. 848-853
Abstract—Generalizing a construction of Silverman, we describe a redundant representation of finite fields GF(qn), where computations in GF (qn) are realized through computations in a suitable residue class algebra. Our focus is on fields of characteristic \ne 2 and we show that the representation discussed here can, in particular, be used for designing a highly regular multiplication circuit for GF (qn).
[1] J.H. Silverman, “Fast Multiplication in Finite Fields$\big. {\rm GF}(2^N)\bigr.$,” Proc. Cryptographic Hardware and Embedded Systems, First Int'l Workshop (CHES '99), ÇK. Koçand C. Paar, eds., pp. 122-134, 1999.
[2] G. Drolet, “A New Representation of Elements of Finite Fields$\big. {\rm GF}(2^m)\bigr.$Yielding Small Complexity Arithmetic Circuits,” IEEE Trans. Computers, vol. 47, no. 9, pp. 938-946, Sept. 1998.
[3] T. Itoh and S. Tsujii, “Structure of Parallel Multipliers for a Class of Finite Fields$GF(2^m)$,” Information and Computation, vol. 83, pp. 21-40, 1989.
[4] J.H. Silverman, Rings of Low Multiplicative Complexity Finite Fields and Their Applications, vol. 6, no. 2, pp. 175-191, 2000.
[5] J.K. Wolf, “Efficient Circuits for Multiplying in$\big. {\rm GF}(2^m)\bigr.$for Certain Values of$\big. m\bigr.$,” Discrete Math., vols. 106/107, pp. 497-502, 1992.
[6] H. Wu, M.A. Hasan, and I.F. Blake, “Highly Regular Architectures for Finite Field Computation Using Redundant Basis,” Proc. Cryptographic Hardware and Embedded Systems, First Int'l Workshop (CHES '99), ÇK. Koçand C. Paar, eds., pp. 269-279, 1999.
[7] W. Geiselmann, J. Müller-Quade, and R. Steinwandt, On 'A New Representation of Elements of Finite Fields${\rm GF}(2^m)$Yielding Small Complexity Arithmetic Circuits' IEEE Trans. Computers, vol. 51, no. 12, pp. 1460-1461, Dec. 2002.
[8] W. Geiselmann and H. Lukhaub, “Redundant Representation of Finite Fields,” Proc. Public Key Cryptography, Fourth Int'l Workshop Practice and Theory in Public Key Cryptosystems (PKC 2001), K. Kim, ed. pp. 339-352, 2001.
[9] W. Geiselmann and R. Steinwandt, A Reversible Redundant Representation of Extension Fields of${\rm GF}(2^m)$ 3. Kolloquium des Schwerpunktprogramms der Deutschen Forschungsgemeinschaft VIVA Grundlagen und Verfahren verlustarmer Informationsverarbeitung, D. Müller, C. Kretzschmar, and R. Siegmund, eds., pp. 98-104, 2002.
[10] M. Ciet and J.-J. Quisquater, F. Sica, A Secure Family of Composite Finite Fields Suitable for Fast Implementation of Elliptic Curve Cryptography Proc. Indocrypt 2001, pp. 108-116, Dec. 2001.
[11] P. Barreto and H. Kim, Fast Hashing onto Elliptic Curves over Fields of Characteristic 3 Cryptology ePrint Archive: Report 2001/098, 2001, http://eprint.iacr.org/2001098/.
[12] D. Boneh, B. Lynn, and H. Shacham, Short Signatures from the Weil Pairing Advances in Cryptology Proc. ASIACRYPT 2001, C. Boyd, ed., pp. 514-532, 2001.
[13] N.P. Smart and E.J. Westwood, Point Multiplication on Ordinary Elliptic Curves over Fields of Characteristic Three Cryptology ePrint Archive, Report 2002/114, 2002, http://eprint.iacr.org/2002114/.
[14] D.V. Bailey and C. Paar, Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Cryptography J. Cryptology, vol. 14, pp. 153-176, 2001.
[15] J. Guajardo and C. Paar, Itoh-Tsujii Inversion in Standard Basis and Its Application in Cryptography and Codes Designs, Codes and Cryptography, vol. 25, no. 2, pp. 207-216, 2002.
[16] W. Bosma, J. Cannon, and C. Playoust, “The Magma Algebra System I: The User Language,” J. Symbolic Computation, vol. 24, pp. 235-265, 1997.
Index Terms:
Galois field arithmetic, VLSI implementation.
Citation:
Willi Geiselmann, Rainer Steinwandt, "A Redundant Representation of GF(q^n) for Designing Arithmetic Circuits," IEEE Transactions on Computers, vol. 52, no. 7, pp. 848-853, July 2003, doi:10.1109/TC.2003.1214334
