Page 8 - Hardware Implementation of Finite-Field Arithmetic

Co n t e n t s vii

5.4 Optimal Extension Fields . . . . . . . . . . . . . . . . . 132
5.5 FPGA Implementations . . . . . . . . . . . . . . . . . . 136
5.5.1 Adders of Polynomials mod p . . . . . . 136
5.5.2 Subtractors of Polynomials
mod p . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.5.3 Adders/Subtractors of Polynomials
mod p . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.5.4 Serial Multipliers . . . . . . . . . . . . . . . . . 137
5.5.5 Exponentiation . . . . . . . . . . . . . . . . . . . 137
5.6 Comments and Conclusions . . . . . . . . . . . . . . 138
5.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6 Operations over GF(p ) . . . . . . . . . . . . . . . . . . . . . . . 139
m
6.1 Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . 140
6.2 Binary Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 147
6.3 Reduction to Multiplications over GF(p )
m
and Inversion over Z . . . . . . . . . . . . . . . . . . . . 154
p
6.4 Optimal Extension Fields . . . . . . . . . . . . . . . . . 156
6.5 FPGA Implementations . . . . . . . . . . . . . . . . . . 162
6.6 Comments and Conclusions . . . . . . . . . . . . . . 162
6.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

7 Operations over GF(2 )—Polynomial Bases . . . . . . 163
m
7.1 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7.1.1 Two-Step Classic Multiplication . . . . 164
7.1.2 Karatsuba-Ofman Polynomial
Multiplication . . . . . . . . . . . . . . . . . . . 169
7.1.3 Interleaved Multiplication . . . . . . . . . 171
7.1.4 Matrix-Vector Multipliers . . . . . . . . . . 174
7.1.5 Montgomery Multiplication . . . . . . . 182
7.2 Squaring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.3 Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . 195
7.4 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
7.5 Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
7.6 Important Irreducible Polynomials . . . . . . . . 213
7.6.1 Equally Spaced Polynomials
(ESPs) . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.6.2 General Irreducible Polynomials . . . 214
7.6.3 All-One Polynomials (AOPs) . . . . . . . 216
7.6.4 Trinomials . . . . . . . . . . . . . . . . . . . . . . . 219
7.6.5 Pentanomials . . . . . . . . . . . . . . . . . . . . 221
7.7 FPGA Implementations . . . . . . . . . . . . . . . . . . 223
7.7.1 Classic Multipliers . . . . . . . . . . . . . . . . 224
7.7.2 Interleaved Multiplication . . . . . . . . . 224
7.7.3 Mastrovito Multipliers . . . . . . . . . . . . 224