AALProject2010

Factorization of polynomial over finite field and irreducibility tests
Finding the factorization of a polynomial over a finite field is of interest not only independently but also for many applications in computer algebra, coding theory, cryptography and computational number theory.

Let F be a finite field. A polynomial f(x) from F[x] that is neither the zero polynomial nor a unit in F[x] is said to be irreducible over F if, whenever f(x) is expressed as a product f(x)=g(x)h(x), with g(x) and h(x) from F[x], then g(x) or h(x) is a unit in F[x].A nonzero, non unit element of F[x] that is not irreducible over F is called reducible over F.

Introduction

A Factor of polynomial P(x) of degree n is a polynomial Q(x) of degree less than n which can be multiplied by another polynomial R(x) of degree less than n to yield P(x) i.e. a polynomial Q(x) such that

             P(x)=Q(x)R(x)

For example, since

               $x^{2}-1=(x+1)(x-1)$, both (x+1) & (x-1) are factors of $x^{2}-1$

Polynomial factorization can be performed...Factorization over an algebraic field is implemented... The coefficient of factorization polynomial are from the finite field...

Finite Field

The theory of finite fields, whose origins can be traced back to the works of Gauss and Galois, has played a part in various branches of mathematics, in recent years there has been a resurgence of interest in finite fields, and this is partly due to important applications in coding theory and cryptography. Applications of Finite Fields introduces some of these recent developments.

A finite field is a field with a finite field order.(i.e. number of element), also called a Galois field. The order of a finite field is always a prime or a power of a prime.For each prime power, there exist exactly one finite field GF($p$), often written as $F_{p}$ in correct usage. GF(p) is called the prime field or order p, and is the field of residuel classes modulo p, where the p elemnet are denoted 0,1,...p-1.a=b in GF(p) means the same as a=b(modp).

Rabin test of irreducibility

Rabin(1980): f is irreducible if and only if gcd(f,x^{q^n/p_i}-x)=1 for all 1≤i≤k, and $x^{q}*n-x$=mod f. Irreducible polynomials are useful for several application:Pseudorandom number generators using feedback shift registers, discrete logarithm over $F_{(}2^{n})$ and efficient arithmetic in finite fields.

Reference

• KEMPFERT,H(1969)On the Factorization of Polynomials Departement of Mathematics, The Ohio State University,Columbus,Ohio 43210
• Shoup,Victor(1996) Smoothness and Factoring Polynomials over Finite Fields Computer Science Department University of Toronto