Welcome to Hardware Implementation of Finite-Field Arithmetic Web site.

In this page you can find VHDL codes and other relevant information related with this book.

The book is published by McGraw Hill, March 2009. ISBN: 978-0-0715-4581-5

Short description (Preface of Book)

Finite fields are used in different types of computers and digital communication systems. Two well-known examples are error-correction codes and cryptography. The traditional way of implementing the corresponding algorithms is software, running on general-purpose processors or on digital-signal processors. Nevertheless, in some cases the time constraints cannot be met with instruction-set processors, and specific hardware must be considered, that is, circuits specifically designed for executing those complex algorithms: they implement the particular computation primitives of the algorithms and take profit of their inherent parallelism.

Apart from the Application Specific Integrated Circuits (ASIC) solution, another technology at hand for developing specific circuits is constituted by Field Programmable Gate Arrays (FPGA). They form an attractive option for small production quantities as their non-recurrent engineering costs are much lower than those corresponding to ASIC's. They also offer flexibility and fast time-to-market. Furthermore, in order to reduce their size, and so the unit cost, an interesting possibility is to reconfigure them at run time so that the same programmable device can execute different predefined functions.

This book describes algorithms and circuits for executing the main finite-field operations, that is, addition, subtraction, multiplication, squaring, exponentiation, and division. It mainly addresses to hardware engineers involved in the development of embedded systems, including finite-field operations. The book distinguishes itself with the following aspects:

The emphasis is different from the classic texts on finite fields. It is not limited to the description of algebraic and algorithmic aspects. The main topic is circuit synthesis.

A special importance has been given to FPGA implementations. The particular architecture of those components leads the designer to use synthesis techniques somewhat different to the ones applied for ASIC for which standard cell libraries exist. All along the book examples of FPGA implementation are described.

Most algorithms are described in Ada, a programming language similar to VHDL, so that they can be executed and the correctness of the proposed algorithms can be verified with actual input data.

In what concerns the description of the circuits, logic schemes are presented as well as VHDL models, in such a way that the corresponding circuits can be easily simulated and synthesized.

The book is divided in 10 chapters. The first chapter (mathematical background) gives the main definitions and properties of finite -fields. Chapters 2 to 4 are dedicated to the operations modulo m and to the corresponding circuits: Chapter 2 deals with the modulo m reduction, Chapter 3 with the modulo m addition, subtraction, multiplication, and exponentiation, and Chapter 4 with the modulo p division, being p a prime. Chapters 5 and 6 are dedicated to the operations modulo f(x), being f(x) a polynomial over a finite field, and to the corresponding circuits: Chapter 5 deals with the modulo f(x) addition, subtraction, multiplication, and exponentiation, and Chap.ter 6 with the modulo f(x) division, being f(x) an irreducible polynomial. Chapters 7 to 9 are dedicated to the main arithmetic operations over GF(2m): in Chap.ter 7 polynomial bases are considered (thus, a particular case of the topics dealt with in Chapters. 5 and 6); in Chap.ter 8 normal bases are used, and in Chap.ter 9 dual and triangular bases are considered. The last (tenth) chapter is dedicated to elliptic-curve cryptography, currently one of the main finite-field applications.

There are four appendices. Three of them describe circuits for performing arithmetic operations over some particular fields, namely a prime field GF(2¹⁹² - 2⁶⁴ - 1) in Appendix A, two optimal extension fields GF(239¹⁷) and GF((2³² - 387)⁶) in Appendix B, and two binary extension fields GF(2¹⁶³) and GF(2²³³) in Appendix C. Appendix D is a brief comparison of the syntaxes of Ada and VHDL.

All the chapters, but the first one, include algorithms, circuits, and results of FPGA implementations. The algorithms are described in Ada and the circuits are modeled in VHDL. Complete and executable source files (Ada and VHDL) are available at the author's Web site www.arithmetic-circuits.org.

The table of contents is also here.

This site is under construction apologize us for errors and mistakes