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
[edit]A Factor of polynomial of degree n is a polynomial of degree less than n which can be multiplied by another polynomial of degree less than n to yield i.e. a polynomial such that
P(x)=Q(x)R(x)
For example, since
, both (x+1) & (x-1) are factors of
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
[edit]Suppose in is the polynomial we wish to factor. We can assume that is of the form
where are distinct element of . We need to find a nontrivial factor of . Let be algebra. Let in modulo in . Then evry element in can be written as where is polynomial of degree less than n over .
Let ) in and let and for element in . which is as a subalgebra of under the usual embedding sending in to mod , we hav .
The zero divisor of are precisely those () in where some, but not all, of the are zero. If is a polynomial over with, then is nontrivial divisor of.
For given in there exists a unique monic polynomial of minimum degree in that is zero at. We denote this polynomial with
let
be the prim factorization of . Since is cyclic group, then can be written as linner direct of subgroups where is Smoothness function and is of order. Therefore in can be written as where in . We can compute as fallow:
- =
- =
- =
- is the multiplicative inverse of modulo
Factoring Algorithm
[edit]Factor p-1 and compute b_j , j=1,2...,r.
For the factorization of 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, . Since all are different, there must be some j=1,..r such that the component of are not the same, i.e. is not in .
Compute the least t such that y^{q^t} in F_p. Let a=y^{q^t}, and z=y^{q^{t-1}}.
Since is not in and , we know that t as defind above satisfies 1<t<e. Observe that where are q-th root of a in not all the same.
Compute M_z, the minimum polynomial of z. Let m=degM_z
We must find a root of . 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 az fallows:
Suppose that hte constante term of is b and that the multiplicative inverse of m mod is m'.
- claim that is the q-root of a.
- Write , where v'is some q-th root of a and is q-th root of unity.
- , where k'is Some q-th root of unity.
- Since v'has order dividing , we have , which is also a q-th root of a.
Compute a root of M_z
We find a root of in time 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 .
Finite Field
[edit]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 , often written as in correct usage. 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, means the same as a=b(modp).
Irreducibility of polynomial
[edit]Let be a finite field. A polynomial from that is neither the zero polynomial nor a unit in is said to be irreducible over if, whenever is expressed as a product , with and. from, then or is a unit in .A nonzero, non unit element of that is not irreducible over is called reducible over.
For prime power q and an integer 2≤n, let be a finit field with q element, and 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
[edit]Let in , deg= n, be a polynomial to be tested for irreducibility. Assum that are the distinct prime divisors of n.
Rabin(1980): is irreducible if and only if for all 1≤i≤k, and =mod.
Algorithm: Robin Irreducibility Test Input: A monic polynomial f in of degree n, and 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 be all the prime divisor of n, and denot , for 1≤i≤k polynomial in of degree n is irreducible in if and only if , for 1≤i≤k, and divides .
The basic idea of this algorithm is to compute mod independently for each value by repeated squaring, and then to take the correspondent gcd. There is O(nM(n)lognlogq) operations in and M(n)= nlognloglogn. Irreducible polynomials are useful for several application:Pseudorandom number generators using feedback shift registers, discrete logarithm over and efficient arithmetic in finite fields.
Example
[edit]Let q=1 mod 4and . Take in to be any quadratic nonresidue. Then is irreducible over for all 0≤k. For instance:
i. if q=p=3 mod 8 is prime, then take ;
ii. if q=p=5 mod 12 is a prime, then take ;
iii. if q=p=2 mod 5 is a prime, then take;
Reference
[edit]- 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
[edit]- Some irreducible polynomials http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf