Page 366 - Hardware Implementation of Finite-Field Arithmetic

346 Inde x

mixed-radix numeration system, 38 normal basis (Cont.):
64
mod (2 192 − 2 − 1) reducer, 50 optimal normal bases multiplication,
mod 239 reducer, 49 Type-I, 260
mod m operations, 61 squaring, 238
addition, 61 number
carry-save multiplier, 69 integer, 1
double, add, and reduce, 70 natural, 1
exponentiation, 82 real, 10
Montgomery multiplication, 75 number theory, 1
Montgomery reduction, 77
multiplication, 66 O O
multiply and reduce, 66 OEF, 132
subtraction, 63 operations over GF(p), 91
mod m reducer, FPGA division
implementation, 54 binary algorithm, 100
mod m reduction, 25 Euclidean algorithm, 92
2 − a, 33, 55 Fermat’s theorem, 110
k
Barrett algorithm, 43 plus-minus algorithm, 104
Barrett reduction, 58 operations over GF(p ), 139
m
integer division, 25 division
nonrestoring, 27, 55 binary algorithm, 147
ik
precomputation of 2 mod m, Euclidean algorithm, 140
38, 57 multiplications over GF(p ) and
m
SRT, 29, 55 inversion over Z , 154
p
Montgomery arithmetic, 75 optimal extension field, 156
Montgomery multiplication, 75, optimal extension field , 156
182 order
Montgomery product, 77 of an element, 7, 8
Montgomery reduction, 77
multiplication, 96 P P
multiplier-subtractor, 97 plus-minus algorithm, 104
multiplier point at infinity, 288
carry-save shift-and-add, 67 polynomial, 11
double, add, and reduce, 71, 74 0-degree, 17
modified carry-save, 69 addition, 163
Montgomery product, 79
all-one (AOP), 216
binomial, irreducible, 132
N N coefficient, 11
n-digit to (k + t)-digit reduction, 43 constant, 11
nonadjacent forms, 294 defining, 19
normal basis, 21, 163, 235 equally spaced (ESP), 213
complexity, 242, 259 general irreducible, 214
exponentiation, 249 irreducible, 12, 19, 163
generator, 21, 235 minimal, 19
inversion, 255 monic, 11
Itoh-Tsujii inversion, 257 pentanomial, 221
Massey-Omura multiplication, pentanomial, class 1, 221
238 subtraction, 163
multiplication, 238 trinomial, 219
N-polynomial, 236 zero, 11
normal element, 21, 235, 237 polynomial basis, 21, 163
optimal normal bases, 236, 259 almost inverse algorithm (AIA),
optimal normal bases, Type-I, 236, 210
259 binary exponentiation method, 196
optimal normal bases, Type-II, 236, division, 204
259 exponentiation, 195