Muutke küpsiste eelistusi

Hardware Implementation of Finite-Field Arithmetic [Kõva köide]

  • Formaat: Hardback, 360 pages, kõrgus x laius x paksus: 236x160x29 mm, kaal: 632 g, 0 Illustrations
  • Ilmumisaeg: 16-Apr-2009
  • Kirjastus: McGraw-Hill Professional
  • ISBN-10: 0071545816
  • ISBN-13: 9780071545815
Teised raamatud teemal:
  • Formaat: Hardback, 360 pages, kõrgus x laius x paksus: 236x160x29 mm, kaal: 632 g, 0 Illustrations
  • Ilmumisaeg: 16-Apr-2009
  • Kirjastus: McGraw-Hill Professional
  • ISBN-10: 0071545816
  • ISBN-13: 9780071545815
Teised raamatud teemal:
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
Preface xi
Acknowledgments xiii
Mathematical Background
1(24)
Number Theory
1(7)
Basic Definitions
1(1)
Euclidean Algorithms
2(2)
Congruences
4(4)
Algebra
8(9)
Groups
8(1)
Rings
9(1)
Fields
10(1)
Polynomials
11(4)
Congruences of Polynomials
15(2)
Finite Fields
17(6)
Basic Properties
17(1)
Field Extensions
18(2)
Roots of Irreducible Polynomials
20(1)
Bases of Finite Fields
20(2)
Finite Fields GF(2m)
22(1)
References
23(2)
mod m Reduction
25(36)
Integer Division
25(8)
Digit Recurrence Algorithms
25(2)
Nonrestoring Reducer
27(2)
SRT Reducer
29(4)
Reduction mod 2k-a
33(5)
Precomputation of 2ik mod m
38(5)
Barrett Reduction Algorithm
43(5)
n-Digit to (k + t)-Digit Reduction
43(1)
An Approximation of q
44(4)
Comparison
48(1)
Specific Circuits
49(5)
mod 239 Reducer
49(1)
mod (2192 - 264 - 1) Reducer
50(4)
FPGA Implementation
54(5)
Nonrestoring Reducers
55(1)
SRT Reducers
55(1)
Reduction mod 2k-a
55(2)
Precomputation of 2ik mod m
57(1)
Barrett Reduction
58(1)
Specific Circuits
59(1)
Comments and Conclusions
59(1)
References
60(1)
mod m Operations
61(30)
Addition mod m
61(2)
Subtraction mod m
63(1)
Adder/Subtractor mod m
64(2)
Multiplication mod m
66(16)
Multiply and Reduce
66(4)
Double, Add, and Reduce
70(5)
Montgomery Multiplication
75(6)
Comparison
81(1)
Exponentiation
82(5)
FPGA Implementations
87(1)
mod m Adders/Subtractors
87(1)
mod m Multipliers
87(1)
mod m Exponentiators
88(1)
Comments and Conclusions
88(1)
References
89(2)
Operations over GF(p)
91(26)
Euclidean Algorithm
92(8)
Integer Division
93(3)
Multiplication and Subtraction
96(2)
mod p Division
98(2)
Binary Algorithm
100(4)
Plus-Minus Algorithm
104(6)
Fermat's Little Theorem
110(2)
Comparison
112(1)
FPGA Implementations
113(3)
Euclidean Algorithm
113(1)
Binary Algorithm
114(1)
Plus-Minus Algorithm
114(1)
Fermat's Little Theorem
115(1)
Comments and Conclusions
116(1)
References
116(1)
Operations over Zp[ x]/f(x)
117(22)
Addition and Subtraction mod f(x)
117(4)
Multiplication mod f(x)
121(7)
Two-Step Multiplication
121(2)
Serial Multiplication
123(5)
Exponentiation mod f(x)
128(4)
Optimal Extension Fields
132(4)
FPGA Implementations
136(2)
Adders of Polynomials mod p
136(1)
Subtracters of Polynomials mod p
136(1)
Adders/Subtractors of Polynomials mod p
137(1)
Serial Multipliers
137(1)
Exponentiation
137(1)
Comments and Conclusions
138(1)
References
138(1)
Operations over GF(pm)
139(24)
Euclidean Algorithm
140(7)
Binary Algorithm
147(7)
Reduction to Multiplications over GF(pm) and Inversion over Zp
154(2)
Optimal Extension Fields
156(6)
FPGA Implementations
162(1)
Comments and Conclusions
162(1)
References
162(1)
Operations over GF(2m)---Polynomial Bases
163(72)
Multiplication
164(23)
Two-Step Classic Multiplication
164(5)
Karatsuba-Ofman Polynomial Multiplication
169(2)
Interleaved Multiplication
171(3)
Matrix-Vector Multipliers
174(8)
Montgomery Multiplication
182(5)
Squaring
187(8)
Exponentiation
195(9)
Division
204(2)
Inversion
206(7)
Important Irreducible Polynomials
213(10)
Equally Spaced Polynomials (ESPs)
213(1)
General Irreducible Polynomials
214(2)
All-One Polynomials (AOPs)
216(3)
Trinomials
219(2)
Pentanomials
221(2)
FPGA Implementations
223(8)
Classic Multipliers
224(1)
Interleaved Multiplication
224(1)
Mastrovito Multipliers
224(1)
Mastrovito Multipliers, Second Version
225(1)
Interleaved Multiplication, Advanced Version
225(1)
Montgomery Multipliers
225(2)
Classic Squaring
227(1)
LSB First Squarer, Second Version
227(1)
Montgomery Squarer
228(1)
Binary Exponentiation
228(1)
Montgomery Exponentiation
229(1)
Division
229(1)
Extended Euclidean Algorithm (EEA) for Inversion
229(1)
Modified Almost Inverse Algorithm (MAIA) for Inversion
230(1)
Important Irreducible Polynomials
230(1)
Comments and Conclusions
231(1)
References
231(4)
Operations over GF(2m)---Normal Bases
235(34)
Some Properties of Normal Bases
236(2)
Squaring
238(1)
Multiplication
238(11)
Exponentiation
249(6)
Inversion
255(4)
Optimal Normal Bases
259(5)
FPGA Implementations
264(2)
Multiplier
265(1)
Exponentiation
265(1)
Inversion
266(1)
Type-I Optimal Normal Basis Multiplier with AOPs
266(1)
Comments and Conclusions
266(1)
References
267(2)
Operations over GF(2m)---Other Bases
269(18)
Dual Bases
269(8)
Triangular Bases
277(7)
References
284(3)
An Example of Application---Elliptic Curve Cryptography
287(26)
Public-Key Cryptography
287(1)
Elliptic Curve over a Finite Field
288(2)
Group Law
290(2)
Point Multiplication
292(12)
Definition
292(1)
Basic Algorithms
293(1)
Some Alternative Methods
294(10)
Example of Implementation
304(6)
Computation Resources
305(1)
Point Addition
305(1)
Point Multiplication
306(4)
FPGA Implementation
310(1)
References
311(2)
p = 2192 - 264-1
313(6)
Hexadecimal Representation
313(1)
mod p Reduction
313(1)
Generic Sequential Circuit
313(1)
Specific Combinational Circuit
314(1)
FPGA Implementation
314(1)
mod p Addition and Subtraction
314(1)
mod p Multiplication
315(1)
Generic Circuit
315(1)
Specific Circuit
315(1)
mod p Exponentiation
316(1)
mod p Division
317(2)
Optimal Extension Fields
319(12)
GF(23917)
319(2)
VHDL Models and Constant Definitions
319(1)
FPGA Implementations
320(1)
GF((232 - 387)6)
321(10)
Constants
321(2)
mod p Reduction
323(1)
mod p Addition and Subtraction
323(1)
mod p Multiplication
324(1)
mod p Division
324(1)
mod (x6 - 2) Multiplication
325(1)
mod (x6 - 2) Division
326(5)
Binary Fields
331(6)
GF(2163)
331(2)
mod f(x) Multiplication
331(1)
mod f(x) Division
331(1)
Squaring
332(1)
Elliptic-Curve Operations
332(1)
GF(2233)
333(4)
mod f(x) Multiplication
333(1)
mod f(x) Division
334(1)
Squaring
334(1)
Elliptic-Curve Operations
334(3)
Ada versus VHDL
337(4)
Index 341
Jean-Pierre Deschamps (Tarragone, Spain) received an MS degree in electrical engineering from the University of Louvain, Belgium, in 1967, the PhD in computer science from the Autonomous University of Barcelona, Spain, in 1983, and a PhD degree in electrical engineering from the Polytechnic School of Lausanne, Switzerland, in 1984. He is currently a professor at the University Rovira i Virgili, Tarragona, Spain. His research interests include ASIC and FPGA design, digital arithmetic and cryptography. He is the author of seven books and about a hundred international papers.