Page 6 - Hardware Implementation of Finite-Field Arithmetic

Contents

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
1 Mathematical Background . . . . . . . . . . . . . . . . . . . . . 1
1.1 Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Basic Definitions . . . . . . . . . . . . . . . . . 1
1.1.2 Euclidean Algorithms . . . . . . . . . . . . . 2
1.1.3 Congruences . . . . . . . . . . . . . . . . . . . . . 4
1.2 Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Groups . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.4 Polynomials . . . . . . . . . . . . . . . . . . . . . 11
1.2.5 Congruences of Polynomials . . . . . . . 15
1.3 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.1 Basic Properties . . . . . . . . . . . . . . . . . . 17
1.3.2 Field Extensions . . . . . . . . . . . . . . . . . . 18
1.3.3 Roots of Irreducible Polynomials . . . 20
1.3.4 Bases of Finite Fields . . . . . . . . . . . . . . 20
m
1.3.5 Finite Fields GF(2 ) . . . . . . . . . . . . . . . 22
1.4 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 mod m Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1 Integer Division . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Digit Recurrence Algorithms . . . . . . . 25
2.1.2 Nonrestoring Reducer . . . . . . . . . . . . 27
2.1.3 SRT Reducer . . . . . . . . . . . . . . . . . . . . . 29
2.2 Reduction mod 2 − a . . . . . . . . . . . . . . . . . . . . . 33
k
2.3 Precomputation of 2 mod m . . . . . . . . . . . . . . 38
ik
2.4 Barrett Reduction Algorithm . . . . . . . . . . . . . . 43
2.4.1 n-Digit to (k + t)-Digit Reduction . . . 43
2.4.2 An Approximation of q . . . . . . . . . . . . 44
2.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.6 Specific Circuits . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.6.1 mod 239 Reducer . . . . . . . . . . . . . . . . . 49
64
2.6.2 mod (2 192 − 2 − 1) Reducer . . . . . . . . 50
2.7 FPGA Implementation . . . . . . . . . . . . . . . . . . . 54
2.7.1 Nonrestoring Reducers . . . . . . . . . . . . 55
2.7.2 SRT Reducers . . . . . . . . . . . . . . . . . . . . 55
2.7.3 Reduction mod 2 − a . . . . . . . . . . . . . . 55
k
v