Introduction to Cryptography with Open-Source Software

230 Cryptography with Open-Source Software

9.7 Multiplication and inversion

Although the product of two polynomials q(x) and r(x) has been defined

to be q(x)r(x) (mod p(x)) where p(x) is an irreducible polynomial, there is

an easier way in practice. Start by setting up a table where every non-zer o

polynomial corresponds to a power of x.

Since by definition of modulus,

x

3

+ x + 1 = 0 (mod x

3

+ x + 1)

it follows immediately that

x

3

= x + 1 (mod x

3

+ x + 1).

So a table can be constructed consisting of increasing powers of x. To go from

one power to the next, multiply its polynomial by x, and whenever there is

an x

3

term, replace it with x + 1:

x

0

= 1

x

1

= x

x

2

= x

2

x