Introduction to Cryptography with Open-Source Software

Finite fields 235

and p. For example, to co mpute

(x

2

+ 1)(x

2

+ x) (mod x

3

+ x + 1)

the bit strings are

a = 1 0 1

b = 1 1 0

p = 1 0 1 1.

Note that in the field GF (2

n

), both a and b will have length n (appending

zeros on the left if nece ssary), and p will have length n + 1. To perform the

multiplication, first enumerate the strings corresponding to all products o f the

form

b

k

= x

k

b(x), for 0 ≤ k ≤ n − 1

and then XOR all strings corresponding to the powers in a(x).

Enumerating the strings is as follows:

1. k = 0: b

0

= x

k

b(x) is just the string b.

2. Given the s tring b

k

correspo nding to x

k

b(x), the string b

k+1

correspo nd-

ing to x

k+1

b(x) is obtained as fo llows:

Append a zero to the end of b

k

to make a string of length n + 1. If the

first element is zero, then b

k+1 ...