Let us now consider the problem of *factoring* polynomials, not merely finding the greatest common divisor of two or more of them.

**Factoring modulo** **p****.** As in the case of integer numbers (Sections 4.5.2, 4.5.4), the problem of factoring seems to be more difficult than finding the greatest common divisor. But factorization of polynomials modulo a prime integer *p* is not as hard to do as we might expect. It is much easier to find the factors of an arbitrary polynomial of degree *n*, modulo 2, than to use any known method to find the factors of an arbitrary *n*-bit binary number. This surprising situation is a consequence of an instructive factorization algorithm discovered in 1967 by Elwyn R. Berlekamp [*Bell System ...*

Start Free Trial

No credit card required