Page 367 - Hardware Implementation of Finite-Field Arithmetic

Index 347

polynomial basis (Cont.): root adjunction, 19
extended Euclidean algorithm, 207 roots, 163, 236
interleaved multiplication, 171 RSA, 287
inversion, 206
Karatsuba-Ofman multiplication, S S
169 semigroup, 8
least-significant bit (LSB) standard basis. See polynomial basis
multiplication, 172 standard projective coordinates,
LSB-first squaring, 187, 192 298
Mastrovito multiplication, 174 step function, 175
Mastrovito product matrix, 174, 217 stored carry encoding, 30
matrix-vector multiplication, 174 subexpression sharing, 178
Montgomery exponentiation subfield, 10
method, 199 proper, 10
Montgomery multiplication, 182 subring, 9
Montgomery squaring, 188 subtraction, 96
most-significant bit-serial (MSB)
multiplication, 172 T T
multiplication, 164 Toeplitz matrix, 179
with AOPs, 216 trace, 20, 237, 269
with ESPs, 213 triangular basis, 277
with general irreducible conversion, 277, 282, 283
polynomials, 214 inversion, 278
with pentanomials, 221 multiplication, 282
with trinomials, 219 transformation matrix, 277
polynomial multiplication,
164, 165 U U
reduction matrix, 166 unity element, 8
reduction modulo an irreducible
polynomial, 164, 166 V V
squaring, 187
two-step classic multiplication, 164 vector space, 19
two-step classic squaring, 187 dimension, 19
prime, 2
pseudo-Mersenne, 132 W W
relatively, 6 Weierstrass equation, 288
prime field, 10
primitive element, 7 Z Z
projective coordinates, 294
projective point, 295 Z , 5
n
*
López-Dahab coordinates, 295 Z , 6
n
standard coordinates, 298 Z [x]/f(x), 117
p
pseudo-Mersenne prime, 132 addition, 117
public key cryptography, 287 exponentiation, 128
least-significant element (LSE) first
multiplication, 125
Q Q most-significant element (MSE) first
quotient, 1, 2, 11 multiplication, 123
multiplication, 121
R R polynomial multiplication, 121,
remainder, 1, 2, 11 122
ring, 9 reduction matrix, 122
commutative, 9, 16, 117 reduction modulo f(x), 121,
polynomial, 11 122
root(s), 20 serial multiplication, 123
adjunction, 20 subtraction, 117
of irreducible polynomial, 20 two-step multiplication, 121