User:Crypto2010

The page is now in progress...
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.

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...

Factorization Polynomial over Finite Field

Suppose$f$ in $F_{p}$is the polynomial we wish to factor. We can assume that$f$ is of the form

         $f=(X-a_{1}).....(X-a_{n})$

where $a_{i}$ are distinct element of $F_{p}$. We need to find a nontrivial factor of $f$. Let$R$ be $F_{p}$ algebra. Let$x$ in$X$ modulo $f$ in $R$. Then evry element in$R$ can be written as $g(x)$ where $g(x)$ is polynomial of degree less than n over $F_{p}$.

Let $u=(u_{1},...u_{n}$) in $F_{p}$ and let $x=(a_{1},...,a_{i})$ and for element $a$ in $F_{p}$. which is as a subalgebra of $R$ under the usual embedding sending $a$ in $F_{p}$ to $a$ mod $f$, we hav $a=(a,...,a)$.

The zero divisor of$R$ are precisely those ($u=u_{1},...u_{n}$) in$R$ where some, but not all, of the $u_{i}$ are zero. If $g$ is a polynomial over $F_{p}$ with$g(x)=u$, then $gcd(f,g)$ is nontrivial divisor of$f$.

For given$u$ in$R$ there exists a unique monic polynomial of minimum degree in $F_{p}[X]$ that is zero at$u$. We denote this polynomial with $M_{u}$

                        $M_{u}=(X-a).....(X-a)$

let

                $p-1=q_{1}^{e_{1}}.....q_{i}^{e_{i}}$

be the prim factorization of $p-1$. Since $F_{p}^{*}$ is cyclic group, then $F_{p}^{*}$ can be written as linner direct of subgroups $S_{1},..S_{r}$ where $S$ is Smoothness function and $S_{j}$ is of order$q_{j}^{e_{j}}$. Therefore $a$ in $F_{p}^{*}$ can be written as $a=a^{1}a^{2}...a^{r}$ where $a^{j}$ in $S_{j}$. We can compute $a^{j}$ as fallow:

• $a^{j}$=$a^{b_{j}}$

• $b_{j}$=$c_{j}d_{j}$

• $d_{j}$=${\frac {(p-1)}{q_{j}^{e_{j}}}}$

• $c_{j}$ is the multiplicative inverse of $d_{j}$ modulo $q_{j}^{e_{j}}$

Factoring Algorithm

        Factor p-1 and compute b_j , j=1,2...,r.

For the factorization of $p-1$ use the Pollard- strassen.

        Compute x^b_j, j=1,..r and from among these select one x^b_j that is not in F_p. For this j. let y=x^b_j, q=q_j, e=e_j.

For any given j, $x^{b_{j}}=(a^{j},....,a^{j})$. Since all $a_{i}$ are different, there must be some j=1,..r such that the component of $x^{b_{j}}$ are not the same, i.e. $x^{b_{j}}$ is not in $F_{p}$.

        Compute the least t such that y^{q^t} in F_p. Let a=y^{q^t}, and z=y^{q^{t-1}}.

Since $y^{q^{t}}$ is not in $F_{p}$ and $y^{q^{t}}=1$, we know that t as defind above satisfies 1<t<e. Observe that $z=(z_{1},...,z_{n})$ where $z_{i}$ are q-th root of a in $F_{p}$ not all the same.

       Compute M_z, the minimum polynomial of z. Let m=degM_z

We must find a root of $M_{z}$. Befor we do this. We do the fallowing:

       Compute a q-th root v of a in F_p

We can find a q-th root of a in time $(nlogp)^{O}(1)$ az fallows:

Suppose that hte constante term of $M_{z}$ is b and that the multiplicative inverse of m mod $q^{e}$ is m'.

• claim that $v=((-1)^{m}*b)^{m'}$ is the q-root of a.
• Write $M_{z}=(X-k_{1}v')...(X-k_{m}v')$, where v'is some q-th root of a and $k_{i}$ is q-th root of unity.
• $b=(-1)^{m}*k'(v')^{m}$, where k'is Some q-th root of unity.
• Since v'has order dividing $q^{e}$, we have $v=((-1)^{m}*b)^{m'}=(k')^{m}v'$, which is also a q-th root of a.

        Compute a root of M_z

We find a root of $M_{z}$ in time $q^{\frac {1}{2}}*(nlogp)^{O}(1)$ as fallows. We shall require primitive q-th root of unity, call k. Under the assumtion of the ERH, with Ankeny'stheorem we can obtain k in time $(nlogp)^{O}(1)$.

Finite Field

The theory of finite fields, whose origins can be traced back to the works ofGauss andGalois, 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).

Irreducibility of polynomial

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$.

For prime power q and an integer 2≤n, let $F_{q}$ be a finit field with q element, and $F_{q^{n}}$ be its extension of degree n. One way to constructing extension of finit field is via an irreducible polynomial over the ground field with degree equal to the degree of the extension. The central idea is to take polynomials at random and test them for irreducibility.

Rabin test of irreducibility

Let $f$ in $F_{q}$, deg$f$= n, be a polynomial to be tested for irreducibility. Assum that $p_{1},p_{2},...,p_{k},$are the distinct prime divisors of n.

Rabin(1980): $f,$ is irreducible if and only if $gcd(f,x^{\frac {q^{n}}{p_{i}}}-x)=1$ for all 1≤i≤k, and $x^{q^{n}}-x$=mod$f$.

 Algorithm: Robin Irreducibility Test
 Input:  A monic polynomial f in $F_{q}[x]$ of degree n, and $p_{1},p_{2},...p_{k}$ all distinct prime divisor of n.
 Output: Either  f is irreducible or f is reducible.
 for j=1 to k do 
 n_j=n/p_j;
 for i=1 to k do 
 g=gcd(f,x^{q^n/p_i}-x)=1
 g= gcd(f,x{q^n/p_i}-x mod f);
 endfor;
 g= xq^n/p_i-x mod f;
 if g=0, then f is irreducible, els f is reducible.

The Robin's algorithm is based on the following fact:

Let $p_{1},p_{2},...,p_{k},$ be all the prime divisor of n, and denot $n/p_{i}=n_{i}$, for 1≤i≤k polynomial$f$ in $F_{q}[x]$of degree n is irreducible in$F_{q}[x]$ if and only if $gcd(f,x^{\frac {q^{n}}{p_{i}}}-x)=1$, for 1≤i≤k, and $f$ divides $x^{q^{n}}-x$.

The basic idea of this algorithm is to compute $x^{q^{n_{i}}}$ mod$f$ independently for each value$n_{1},n_{2},...n_{k}$ by repeated squaring, and then to take the correspondent gcd. There is O(nM(n)lognlogq) operations in $F_{q}$ and M(n)= nlognloglogn. 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.

Example

Let q=1 mod 4and $n=2^{k}$. Take $a$ in $F_{q}$ to be any quadratic nonresidue. Then $x^{2^{k}}-a$ is irreducible over $F_{q}$ for all 0≤k. For instance:

i. if q=p=3 mod 8 is prime, then take $a=2$;

ii. if q=p=5 mod 12 is a prime, then take $a=3$;

iii. if q=p=2 mod 5 is a prime, then take$a=5$;

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
• Von Zur Gathen, J., Panario, D. Factoring Polynomials Over Finite Fields: A Survey (2001). Fachbereich Mathematik-Informatik, Universitat Paderborn. Department of Computer Science, University of Toronto.
• Gao Shuhong , Panario Daniel,Test and Construction of Irreducible Polynomials over Finite Fields Department of mathematical Sciences, Clemson University, South Carolina, 29634-1907, USA. and Department of computer science University of Toronto, canada M5S-1A4

Notes

• Some irreducible polynomials http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf