Page 364 - Hardware Implementation of Finite-Field Arithmetic

344 Inde x

algorithm (Cont.): congruence, 4
polynomial basis classic squaring, class, 5
187, 188 modulo f(x), 15
polynomial basis inversion, AIA, modulo n, 4
207, 208, 210, 211 properties, 5
polynomial basis LSB-first of polynomials, 15
multiplier, 172 conjugate, 20, 236
polynomial basis LSB-first squaring,
187, 193 D D
polynomial basis Mastrovito defining element, 19
multiplication, 177, 180 deg. See degree
for AOPs, 217 degree, polynomial, 11
for class 1 pentanomials, 223 discrete logarithm system, 287
for trinomials, 220 divider
polynomial basis Montgomery binary algorithm, 102, 152
exponentiation, 200 Euclidean algorithm, 99, 145
polynomial basis Montgomery Fermat’s theorem, 110
multiplication, 183, 184 multiplications over GF(p ) and
m
polynomial basis Montgomery inversion over Z , 155
squaring, 188, 190 nonrestoring, 95 p
polynomial basis MSB-first optimal extension field, 159
multiplier, 172 plus-minus algorithm, 107
ik
precomputation of 2 mod m, 40 division
shift and add multiplication, 66 integer, 2
SRT algorithm, 31 integer division, 93
subtract and shift, 97 mod f(x)
triangular basis inversion for binary algorithm, 147
m
GF(2 ), 281 Euclidean algorithm, 140
triangular basis multiplication for multiplications over GF(p ) and
m
GF(2 ), 282, 283 inversion over Z , 154
m
p
Z [x]/f(x) addition, 117, 118 optimal extension field, 156
p
Z [x]/f(x) binary exponentiation,
p mod p
129 binary algorithm, 100
Z [x]/f(x) LSE-first multiplier, 126
p Euclidean algorithm, 98
Z [x]/f(x) MSE-first multiplier, 124 Fermat’s theorem, 110
p
Zp[x]/f(x) multiplication, 123 plus-minus algorithm, 104
Z [x]/f(x) subtraction, 118, 119 divisor, 1, 12
p
AOP, 216 dual basis, 21, 269
automorphism, 21 convenient dual basis, 273
Frobenius, 21 conversion, 4
inverse, 275
B B multiplication, 270
basis, 20 optimal dual bases, 273
dual, 21 pentanomial, 273
normal, 21 squaring, 274
polynomial, 21 trinomial, 273
Berlekamp multiplier, 271 weakly dual bases, 270
Bezout’s identity, 182 duality, 21, 269
binary algorithm, 91, 100, 204
binary extension field, 22, 163, 235 E E
elliptic curve, 288
C C Hasse theorem, 289
canonical basis. See polynomial basis Koblitz, 299
carry-free operations, 30 nonsupersingular, 289
cofactor, 292 projective form, 295
coefficient, leading, 11 supersingular, 289