Page 7 - Hardware Implementation of Finite-Field Arithmetic

vi Co n t e n t s

ik
2.7.4 Precomputation of 2 mod m . . . . . . . 57
2.7.5 Barrett Reduction . . . . . . . . . . . . . . . . 58

2.7.6 Specific Circuits . . . . . . . . . . . . . . . . . . 59
2.8 Comments and Conclusions . . . . . . . . . . . . . . 59
2.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3 mod m Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.1 Addition mod m . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Subtraction mod m . . . . . . . . . . . . . . . . . . . . . . 63
3.3 Adder/Subtractor mod m . . . . . . . . . . . . . . . . 64
3.4 Multiplication mod m . . . . . . . . . . . . . . . . . . . . 66
3.4.1 Multiply and Reduce . . . . . . . . . . . . . 66
3.4.2 Double, Add, and Reduce . . . . . . . . 70
3.4.3 Montgomery Multiplication . . . . . . . 75
3.4.4 Comparison . . . . . . . . . . . . . . . . . . . . . 81
3.5 Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.6 FPGA Implementations . . . . . . . . . . . . . . . . . . 87
3.6.1 mod m Adders/Subtractors . . . . . . . . 87
3.6.2 mod m Multipliers . . . . . . . . . . . . . . . . 87
3.6.3 mod m Exponentiators . . . . . . . . . . . . 88
3.7 Comments and Conclusions . . . . . . . . . . . . . . 88
3.8 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4 Operations over GF(p) . . . . . . . . . . . . . . . . . . . . . . . . 91
4.1 Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . 92
4.1.1 Integer Division . . . . . . . . . . . . . . . . . . 93
4.1.2 Multiplication and Subtraction . . . . . 96
4.1.3 mod p Division . . . . . . . . . . . . . . . . . . 98
4.2 Binary Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 100
4.3 Plus-Minus Algorithm . . . . . . . . . . . . . . . . . . . 104
4.4 Fermat’s Little Theorem . . . . . . . . . . . . . . . . . . 110
4.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.6 FPGA Implementations . . . . . . . . . . . . . . . . . . 113
4.6.1 Euclidean Algorithm . . . . . . . . . . . . . . 113
4.6.2 Binary Algorithm . . . . . . . . . . . . . . . . . 114
4.6.3 Plus-Minus Algorithm . . . . . . . . . . . . 114
4.6.4 Fermat’s Little Theorem . . . . . . . . . . . 115
4.7 Comments and Conclusions . . . . . . . . . . . . . . 116
4.8 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5 Operations over Z [x]/f(x) . . . . . . . . . . . . . . . . . . . . . 117
p
5.1 Addition and Subtraction mod f(x) . . . . . . . . . 117
5.2 Multiplication mod f(x) . . . . . . . . . . . . . . . . . . 121
5.2.1 Two-Step Multiplication . . . . . . . . . . . 121
5.2.2 Serial Multiplication . . . . . . . . . . . . . . 123
5.3 Exponentiation mod f(x) . . . . . . . . . . . . . . . . . 128