Hardware implementation of Finite Field Division

Acta Applicandae Mathematicae – Special Issue on “Finite Fields: Applications and Implementations”

In this page you can found the VHDL codes and ADA models of the article:

Hardware implementation of Finite Field Division, published in Acta Applicandae Mathematicae – Special Issue on “Finite Fields: Applications and Implementations”. ISSN: 0167-8019. http://www.springerlink.com/content/432226260818jxl3/

Paper Abstract

Algorithms for performing divisions over Zp and GF(pm) are described, the corresponding digital circuits are synthesized and conclusions about their computation times are drawn. The results of their implementation within field-programmable devices are given in the case of the most efficient ones.

ADA models:

All ADA models

For all examples Galoise.adb and Galoise.ads are necessary.

Algorithm 1 (mod p division, Euclidean algorithm)

Algorithm 2 (mod p division, binary algorithm )

Algorithm 3 (mod p division, plus-minus algorithm)

Algorithm 5 (mod p division, algorithm based on the Fermat’s little theorem)

Algorithm 6 (mod f(x) division, Euclidean algorithm)

Algorithm 7 (mod f(x) division, Modified Euclidean algorithm)

Algorithm 9 (mod f(x) division, binary algorithm)

Algorithm 10 (mod f(x) division, binary algorithm, second version)

Algorithm 11 (mod f(x) division, Multiplications over GF(p^m) and inversion over Z_p)

Algorithm 12 (mod f(x) division, Multiplications over GF(p^m) binary field)

Algorithm 13 (mod f(x) division, Multiplications over GF(p^m) and inversion over Z_p, binomial)

Algorithm 14 (mod f(x) division, Multiplications over GF(p^m) and inversion over Z_p, binomial - second version)

VHDL codes:

mod p division

Plus-Minus algorithm. FPGA optimized Code (Xilinx ISE project)

Fermat’s little theorem. Xilinx ISE project

Fermat’s little theorem. For p=239. VHDL code and Simulation (do file)

Fermat’s little theorem. For p=2**192-2**64-1. VHDL code and Simulation (do file)

Fermat’s little theorem. For p=2**32-387. VHDL code and Simulation (do file)

mod f(x) division

Divider over GF(2¹⁶³) based on the irreducible polynomial: f(x) = x¹⁶³ + x⁷ + x⁶ + x³ + 1. Simple ISE project (zip file). Xilinx FPGA optimized project (zip file)

Divider over GF(239¹⁷) based on the irreducible binomial f(x) = x¹⁷ + 237. Simple ISE project (zip file). Xilinx FPGA optimized project (zip file)  

Divider over GF(2¹⁶³) based on the irreducible polynomial: f(x) = x¹⁶³ + x⁷ + x⁶ + x³ + 1. Multiplications over GF(2^m). VHDL file, Simulation (do file). 

Divider over GF(239¹⁷) based on the irreducible binomial f(x) = x¹⁷ + 237. Multiplications over GF(p^m) and inversion over Z_p. VHDL file, Simulation (do file).