## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

Chapter 7

CONSTRUCTING F-REDUCING POLYNOMIALS

### 7.1 Introduction

Let f(x) be a monic polynomial of degree n without repeated factors. We recall from Definition 6.8 that f-reducing polynomials are those polynomials which allow the factorization of f(x). In this chapter, we look into the interesting problem of factorization of polynomials over large finite fields using f-reducing polynomials.

Let f1(x), f2(x), ..., fk(x) be monic irreducible factors in the canonical factorization (see Section 6.3) of f(x) in GF(q) [x], where deg(fi(x)) = ni, 1 ≤ ik. Let N be the least positive integer such that xqNx mod f(x). By Theorem 6.10 it follows that

are f-reducing polynomials. It is immediate to check that

Whenever the order of f(x) is known in advance, ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required