Introduction to Cryptography with Open-Source Software

Finite fields 225

and finding the remainder can be performed by the usual long division of

polynomials, with all arithmetic mod 2:

x

4

+ x

3

x

4

+ x

2

+ x + 1



x

8

+ x

7

+ x

6

+ 0x

5

+ 0x

4

+ 0x

3

+ x

2

+ x + 1

x

8

+ x

6

+ x

5

+ x

4

x

7

+ x

5

+ x

4

x

7

+ x

5

+ x

4

+ x

3

x

3

+ x

2

+ x + 1

and so the result of the division is x

4

+ x

3

, with rema inder x

3

+ x

2

+ x + 1.

Note that to do this it is e asiest to write out all possible powers x

k

, using 0

coefficients for powers not in the original polynomial. Such a polynomial long

division as above can be more easily done by just writing down the coefficients,

and not all the powers:

1 1

1 0 1 1 1



1 1 1 0 0 0 1 1 1

1 0 1 1 1

1 0 1 1 0 1 1 1

1 0 1 1 1

1 1 1 1

The degree of ...