Hardware implementation of finite-field arithmetic

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010193572	TK7895.E42 D474 2009	Open Access Book	Book	Searching... Unknown
Searching... PSZ KL	30000010193571	TK7895.E42 D474 2009	Open Access Book	Book	Searching... Unknown

Summary

Publisher's Note: Products purchased from Third Party sellers are not guaranteed by the publisher for quality, authenticity, or access to any online entitlements included with the product.

Implement Finite-Field Arithmetic in Specific Hardware (FPGA and ASIC)

Master cutting-edge electronic circuit synthesis and design with help from this detailed guide. Hardware Implementation of Finite-Field Arithmetic describes algorithms and circuits for executing finite-field operations, including addition, subtraction, multiplication, squaring, exponentiation, and division.

This comprehensive resource begins with an overview of mathematics, covering algebra, number theory, finite fields, and cryptography. The book then presents algorithms which can be executed and verified with actual input data. Logic schemes and VHDL models are described in such a way that the corresponding circuits can be easily simulated and synthesized. The book concludes with a real-world example of a finite-field application--elliptic-curve cryptography. This is an essential guide for hardware engineers involved in the development of embedded systems.

Get detailed coverage of:

Modulo m reduction Modulo m addition, subtraction, multiplication, and exponentiation Operations over GF(p) and GF(pm) Operations over the commutative ring Zp[x]/f(x)

Operations over the binary field GF(2m) using normal, polynomial, dual, and triangular

Author Notes

Jean-Pierre Deschamps, Ph.D., is a professor at the University Rovira i Virgili in Tarragona, Spain.

José Luis Imaña, Ph.D., is a professor at Complutense University of Madrid, Spain.

Gustavo D. Sutter, Ph.D., is a professor at the Autonomous University of Madrid, Spain.

Preface	p. xi
Acknowledgments	p. xiii
1 Mathematical Background	p. 1
1.1 Number Theory	p. 1
1.1.1 Basic Definitions	p. 1
1.1.2 Euclidean Algorithms	p. 2
1.1.3 Congruences	p. 4
1.2 Algebra	p. 8
1.2.1 Groups	p. 8
1.2.2 Rings	p. 9
1.2.3 Fields	p. 10
1.2.4 Polynomials	p. 11
1.2.5 Congruences of Polynomials	p. 15
1.3 Finite Fields	p. 17
1.3.1 Basic Properties	p. 17
1.3.2 Field Extensions	p. 18
1.3.3 Roots of Irreducible Polynomials	p. 20
1.3.4 Bases of Finite Fields	p. 20
1.3.5 Finite Fields GF(2 m )	p. 22
1.4 References	p. 23
2 mod m Reduction	p. 25
2.1 Integer Division	p. 25
2.1.1 Digit Recurrence Algorithms	p. 25
2.1.2 Nonrestoring Reducer	p. 27
2.1.3 SRT Reducer	p. 29
2.2 Reduction mod 2 k - a	p. 33
2.3 Precomputation of 2 ik mod m	p. 38
2.4 Barrett Reduction Algorithm	p. 43
2.4.1 n-Digit to (k + t)-Digit Reduction	p. 43
2.4.2 An Approximation of q	p. 44
2.5 Comparison	p. 48
2.6 Specific Circuits	p. 49
2.6.1 mod 239 Reducer	p. 49
2.6.2 mod (2 192 - 2 64 - 1) Reducer	p. 50
2.7 FPGA Implementation	p. 54
2.7.1 Nonrestoring Reducers	p. 55
2.7.2 SRT Reducers	p. 55
2.7.3 Reduction mod 2 k - a	p. 55
2.7.4 Precomputation of 2 ik mod m	p. 57
2.7.5 Barrett Reduction	p. 58
2.7.6 Specific Circuits	p. 59
2.8 Comments and Conclusions	p. 59
2.9 References	p. 60
3 mod m Operations	p. 61
3.1 Addition mod m	p. 61
3.2 Subtraction mod m	p. 63
3.3 Adder/Subtractor mod m	p. 64
3.4 Multiplication mod m	p. 66
3.4.1 Multiply and Reduce	p. 66
3.4.2 Double, Add, and Reduce	p. 70
3.4.3 Montgomery Multiplication	p. 75
3.4.4 Comparison	p. 81
3.5 Exponentiation	p. 82
3.6 FPGA Implementations	p. 87
3.6.1 mod m Adders/Subtractors	p. 87
3.6.2 mod m Multipliers	p. 87
3.6.3 mod m Exponentiators	p. 88
3.7 Comments and Conclusions	p. 88
3.8 References	p. 89
4 Operations over GF(p)	p. 91
4.1 Euclidean Algorithm	p. 92
4.1.1 Integer Division	p. 93
4.1.2 Multiplication and Subtraction	p. 96
4.1.3 mod p Division	p. 98
4.2 Binary Algorithm	p. 100
4.3 Plus-Minus Algorithm	p. 104
4.4 Fermat's Little Theorem	p. 110
4.5 Comparison	p. 112
4.6 FPGA Implementations	p. 113
4.6.1 Euclidean Algorithm	p. 113
4.6.2 Binary Algorithm	p. 114
4.6.3 Plus-Minus Algorithm	p. 114
4.6.4 Fermat's Little Theorem	p. 115
4.7 Comments and Conclusions	p. 116
4.8 References	p. 116
5 Operations over Z p [x]/f(x)	p. 117
5.1 Addition and Subtraction mod f(x)	p. 117
5.2 Multiplication mod f(x)	p. 121
5.2.1 Two-Step Multiplication	p. 121
5.2.2 Serial Multiplication	p. 123
5.3 Exponentiation mod f(x)	p. 128
5.4 Optimal Extension Fields	p. 132
5.5 FPGA Implementations	p. 136
5.5.1 Adders of Polynomials mod p	p. 136
5.5.2 Subtractors of Polynomials mod p	p. 136
5.5.3 Adders/Subtractors of Polynomials mod p	p. 137
5.5.4 Serial Multipliers	p. 137
5.5.5 Exponentiation	p. 137
5.6 Comments and Conclusions	p. 138
5.7 References	p. 138
6 Operations over GF(p m )	p. 139
6.1 Euclidean Algorithm	p. 140
6.2 Binary Algorithm	p. 147
6.3 Reduction to Multiplications over GF(p m ) and Inversion over Z p	p. 154
6.4 Optimal Extension Fields	p. 156
6.5 FPGA Implementations	p. 162
6.6 Comments and Conclusions	p. 162
6.7 References	p. 162
7 Operations over GF(2 m )-Polynomial Bases	p. 163
7.1 Multiplication	p. 164
7.1.1 Two-Step Classic Multiplication	p. 164
7.1.2 Karatsuba-Ofman Polynomial Multiplication	p. 169
7.1.3 Interleaved Multiplication	p. 171
7.1.4 Matrix-Vector Multipliers	p. 174
7.1.5 Montgomery Multiplication	p. 182
7.2 Squaring	p. 187
7.3 Exponentiation	p. 195
7.4 Division	p. 204
7.5 Inversion	p. 206
7.6 Important Irreducible Polynomials	p. 213
7.6.1 Equally Spaced Polynomials (ESPs)	p. 213
7.6.2 General Irreducible Polynomials	p. 214
7.6.3 All-One Polynomials (AOPs)	p. 216
7.6.4 Trinomials	p. 219
7.6.5 Pentanomials	p. 221
7.7 FPGA Implementations	p. 223
7.7.1 Classic Multipliers	p. 224
7.7.2 Interleaved Multiplication	p. 224
7.7.3 Mastrovito Multipliers	p. 224
7.7.4 Mastrovito Multipliers, Second Version	p. 225
7.7.5 Interleaved Multiplication, Advanced Version	p. 225
7.7.6 Montgomery Multipliers	p. 225
7.7.7 Classic Squaring	p. 227
7.7.8 LSB First Squarer, Second Version	p. 227
7.7.9 Montgomery Squarer	p. 228
7.7.10 Binary Exponentiation	p. 228
7.7.11 Montgomery Exponentiation	p. 229
7.7.12 Division	p. 229
7.7.13 Extended Euclidean Algorithm (EEA) for Inversion	p. 229
7.7.14 Modified Almost Inverse Algorithm (MAIA) for Inversion	p. 230
7.7.15 Important Irreducible Polynomials	p. 230
7.8 Comments and Conclusions	p. 231
7.9 References	p. 231
8 Operations over GF(2 m )-Normal Bases	p. 235
8.1 Some Properties of Normal Bases	p. 236
8.2 Squaring	p. 238
8.3 Multiplication	p. 238
8.4 Exponentiation	p. 249
8.5 Inversion	p. 255
8.6 Optimal Normal Bases	p. 259
8.7 FPGA Implementations	p. 264
8.7.1 Multiplier	p. 265
8.7.2 Exponentiation	p. 265
8.7.3 Inversion	p. 266
8.7.4 Type-I Optimal Normal Basis Multiplier with AOPs	p. 266
8.8 Comments and Conclusions	p. 266
8.9 References	p. 267
9 Operations over GF(2 m )-Other Bases	p. 269
9.1 Dual Bases	p. 269
9.2 Triangular Bases	p. 277
9.3 References	p. 284
10 An Example of Application-Elliptic Curve Cryptography	p. 287
10.1 Public-Key Cryptography	p. 287
10.2 Elliptic Curve over a Finite Field	p. 288
10.3 Group Law	p. 290
10.4 Point Multiplication	p. 292
10.4.1 Definition	p. 292
10.4.2 Basic Algorithms	p. 293
10.4.3 Some Alternative Methods	p. 294
10.5 Example of Implementation	p. 304
10.5.1 Computation Resources	p. 305
10.5.2 Point Addition	p. 305
10.5.3 Point Multiplication	p. 306
10.6 FPGA Implementation	p. 310
10.7 References	p. 311
A p = 2 192 - 2 64 - 1	p. 313
A.1 Hexadecimal Representation	p. 313
A.2 mod p Reduction	p. 313
A.2.1 Generic Sequential Circuit	p. 313
A.2.2 Specific Combinational Circuit	p. 314
A.2.3 FPGA Implementation	p. 314
A.3 mod p Addition and Subtraction	p. 314
A.4 mod p Multiplication	p. 315
A.4.1 Generic Circuit	p. 315
A.4.2 Specific Circuit	p. 315
A.5 mod p Exponentiation	p. 316
A.6 mod p Division	p. 317
B Optimal Extension Fields	p. 319
B.1 GF(239 17 )	p. 319
B.1.1 VHDL Models and Constant Definitions	p. 319
B.1.2 FPGA Implementations	p. 320
B.2 GF((2 32 - 387) 6 )	p. 321
B.2.1 Constants	p. 321
B.2.2 mod p Reduction	p. 323
B.2.3 mod p Addition and Subtraction	p. 323
B.2.4 mod p Multiplication	p. 324
B.2.5 mod p Division	p. 324
B.2.6 mod (x 6 - 2) Multiplication	p. 325
B.2.7 mod (x 6 - 2) Division	p. 326
C Binary Fields	p. 331
C.1 GF(2 163 )	p. 331
C.1.1 mod f(x) Multiplication	p. 331
C.1.2 mod f(x) Division	p. 331
C.1.3 Squaring	p. 332
C.1.4 Elliptic-Curve Operations	p. 332
C.2 GF(2 233 )	p. 333
C.2.1 mod f(x) Multiplication	p. 333
C.2.2 mod f(x) Division	p. 334
C.2.3 Squaring	p. 334
C.2.4 Elliptic-Curve Operations	p. 334
D Ada versus VHDL	p. 337
Index	p. 341

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents