Page 363 - Hardware Implementation of Finite-Field Arithmetic

φ(n), 6, 7 algorithm (Cont.):
Montgomery exponentiation
A A LSB-first, 85
adders, carry-save, 29 MSB-first, 83
adder-subtractor, 64 Montgomery product, 77, 78
affine point, 295 Montgomery reduction, 77
algorithm n-digit to (k + t)-digit reduction, 44
τ-ary representation, 301 nonrestoring division, 94
k
Barrett reduction, 46 normal basis 2 -ary exponentiation,
digit recurrence carry save 253, 254
reduction, 30 normal basis binary exponentiation,
digit recurrence reduction, 27 250
division, Fermat’s theorem, 110 normal basis inversion, 255
double, add, and reduce, 71, 73 normal basis Itoh-Tsujii inversion,
dual basis inversion for GF(2 ), 276 258
4
dual basis multiplication, 272 normal basis m-ary exponentiation,
8
dual basis multiplication for GF(2 ), 253
274 normal basis Massey-Omura
4
inversion for GF(2 ), 279 multiplication for GF(2 ), 240
m
k
mod 2 − a reduction, 35, 36 normal basis multiplication, 245,
mod f(x) division, binary algorithm, 246
149, 151 normal basis squaring, 238
mod f(x) division, Euclidean OEF binary exponentiation,
algorithm, 141, 142, 143 135
mod f(x) division, multiplications OEF LSE-first multiplier, 135
m
over GF(p ) and inversion over OEF MSE-first multiplier, 135
Z , 154 OEF multiplication, 134
p
mod f(x) division, optimal extension optimal normal basis multiplication,
field, 157, 158 Type-I, 260, 261
mod m addition, 61, 62 point addition, 291
mod m exponentiation, LSB-first, 85 point multiplication, 293
163
mod m exponentiation, MSB-first, GF(2 ), 307
82 Montgomery algorithm, 297
mod m subtraction, 63 τ-ary representation, 302, 303
mod p division, binary algorithm, polynomial basis binary algorithm,
101 204
mod p division, Euclidean polynomial basis binary
algorithm, 92 exponentiation, 196
mod p division, plus-minus polynomial basis classic
algorithm, 106 multiplication, 167
343