O'Reilly logo

Elements of Algebraic Coding Systems by Valdemar Cardoso da Rocha, Jr.

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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.

Start Free Trial

No credit card required