) are polynomials over a field F (or over a ring R with the highest degree coefficient r of P2(z) being the multiplicative identity of R), then there exists polynomials Q(z) and R(z) over F such that Pseudonoise Generators P1(z)=Q(z)P2(z)+R(z), (5A.21) where 0 V deg R(z) , deg P2(z). The polynomial R(z) is often referred to as the value of P1(z) modulo P2(z) or simply P1(z) mod P2(z). Again, if R(z) = 0, we say that P2(z) divides P1(z). We can also define the greatest common divisor of two polynomials P1(z) and P(z) over a field F as the highest degree polynomial dividing both P1(z) and P2(z). By an algorithm identical to that used in the ring of integers (see Section 5A.2), the gcd(P1(z), P2(z)) can be found and shown to be of the form gcd(P1(z), P2(z)) = C1(z)P1(z) + C2(z)P2(z) (5A.22) where C1(z) and C2(z) are polynomials over the same field as P1(z) and P2(z). + + polynomials are over GF(2) and only polynomial coefficients are listed in the following table. The notation is identical to that used for integers earlier. (B (st) 1 (11111111010010011) (11101010001010) (1001) (1000001001001) (0,1) 2 (11101010001010) (1000001001001) (101001010001) (1,1001) 3 (1000001001001) (101001010001) (10011101011) (11,11010) 4 (101001010001) (10011101011) (1110000111) (111,11101) 5 (10011101011) (1110000111) (1100010) (1101,1100000) 6 (1110000111) (1100010) (1011) (110001) (100000,10011101) 7 (1100010) (110001) (10111101, 10100101111) Check: (z541)16114+4++ = Suppose a is an element of a ring which contains the ring R of polyno- mial coefficients. We say that a is root of multiplicity K, of the polynomial P(z) if (z - a)R divides P(z). To determine if a is a root of P(z), long divi- sion can be used, generally resulting in P(z)(z-a)Q(z)+P(a), (5A.23) where the polynomial Q(z) has degree one less than P(z). Hence, we have the following theorem: THEOREM 5A.1 (Factorization Theorem). The element a is a root of P(z) if and only if P(a) = 0.IfP(a) = 0, we can determine if (z - a)2 divides P(z) Appendix 5A. Finite Field Arithmetic by