Szerkesztő:05storm26/Faktorizálás véges test felett

A polinomok faktorizációjának azt az eljárást nevezzük, amelynek során egy polinomot irreducibilis elemek szorzatára bontunk. Ez a felbontás elméletileg mindig lehetséges, és egyértelműen elvégezhető test együtthatós polinomok esetében, de ahhoz, hogy általános algoritmus létezzen a faktorizáció elvégzésére az együtthatók testének egyéb feltételeket is ki kell elégítenie. Valójában ilyen algoritmusok csak bizonyos meghatározott polinomokra léteznek, mint például, amelyek együtthatói olyan véges testből származnak, amely részteste a racionális számtestnek, vagy amely együtthatói a racionális számtest véges számú elemmel generált kiterjesztésének elemei.

A jelen szócikk témája az egyváltozós polinomok véges test fölötti faktorizációja. Ez az eset azért különösen fontos, mivel a bonylultabb algoritmusok erre az esetre redukálják az egyéb típusú polinomok faktorizációját. (Lásd: Polinomok faktorizációja)

Alap információk

szerkesztés

Véges test

szerkesztés

A véges testek elméletének története Gauss és Galois munkájáig követhető vissza. Mivel a téma sok területen alkalmazható a matematikában és más tudományokban is mint például a számítástudomány így a terület kutatására nagy erőket fordítottak.

A véges test vagy Galois test olyan test amely véges sok elemből áll. Egy véges test elemszáma mindig prímszám vagy egy prímszám (egész) hatványa. Minen q = pr prímhatványhoz pontosan egy véges test létezik q elemmel (az izomorfizmustól eltekintve). Ezt a testet GF(q) vagy Fq jelöli. Ha p prím akkor GF(p) prímtest, amelynek p eleme van és ezek mod p szerinti maradékosztályok, amiket 0, 1, ..., p−1-vel jelölünk. Vagyis a = b a GF(p) testben azzal ekvivalens, hogy: ab (mod p).

Irreducibilis polinomok

szerkesztés

Let F be a finite field. As for general fields, a non-constant polynomial f in F[x] is said to be irreducible over F if it is not the product of two polynomials of positive degree. A polynomial of positive degree that is not irreducible over F is called reducible over F.

Irreducible polynomials allow to construct the finite fields of non prime order. In fact, for a prime power q, let Fq be the finite field with q elements, unique up to an isomorphism. A polynomial f of degree n greater than one, which is irreducible over Fq, defines a field extension of degree n which is isomorphic to the field with qn elements: the elements of this extension are the polynomials of degree lower than n; addition, subtraction and multiplication by an element of Fq are those of the polynomials; the product of two elements it the remainder of the division by f of their product as polynomials; the inverse of an element may be computed by the extended GCD algorithm (see Arithmetic of algebraic extensions).

It follows that, to compute in a finite field of non prime order, one needs to generate an irreducible polynomial. For this, the common method is to take a polynomial at random and test it for irreducibility. For sake of efficiency of the multiplication in the field, it is usual to search for polynomials of the shape xn + ax + b.[forrás?]

Irreducible polynomials over finite fields are also useful for Pseudorandom number generators using feedback shift registers and discrete logarithm over F2n.

The polynomial P = x4 + 1 is irreducible over Q but not over any finite field.

  • On any field extension of F2, P = (x+1)4.
  • On every other finite field, at least one of −1, 2 and −2 is a square, because the product of two non squares is a square and so we have
  1. If   then  
  2. If   then  
  3. If   then  

Komplexitás

szerkesztés

Polynomial factoring algorithms use basic polynomial operations such as products, divisions, gcd, powers of one polynomial modulo another, etc. A multiplication of two polynomials of degree at most n can be done in O(n2) operations in Fq using "classical" arithmetic, or in O(nlog(n)) operations in Fq using "fast" arithmetic. A Euclidean division (division with remainder) can be performed within the same time bounds. The cost of a polynomial greatest common divisor between two polynomials of degree at most n can be taken as O(n2) operations in Fq using classical methods, or as O(nlog2(n)) operations in Fq using fast methods. For polynomials h, g of degree at most n, the exponentiation hq mod g can be done with O(log(q)) polynomial products, using exponentiation by squaring method, that is O(n2log(q)) operations in Fq using classical methods, or O(nlog(q)log(n)) operations in Fq using fast methods.

In the algorithms that follow, the complexities are expressed in terms of number of arithmetic operations in Fq, using classical algorithms for the arithmetic of polynomials.

Faktorizációs algoritmusok

szerkesztés

Sok algoritmus a következő három lépésből áll:

Négyzetmentes faktorizáció

szerkesztés

The algorithm determines a square-free factorization for polynomials whose coefficients come from the finite field Fq of order q = pm with p a prime. This algorithm firstly determines the derivative and then computes the gcd of the polynomial and its derivative. If it is not one then the gcd is again divided into the original polynomial, provided that the derivative is not zero (a case that exists for non-constant polynomials defined over finite fields).

This algorithm uses the fact that, if the derivative of a polynomial is zero, then it is a polynomial in xp, which is the pth power of the polynomial obtained by substituting x by x1/p.

This algorithm works also over a field of characteristic zero, with the only difference that it never enters in the blocks of instructions where pth roots are computed. However, in this case, Yun's algorithm is much more efficient because it computes the greatest common divisors of polynomials of lower degrees. A consequence is that, when factoring a polynomial over the integers, the algorithm which follows is not used: one compute first the square-free factorization over the integers, and to factor the resulting polynomials, one chooses a p such that they remain square-free modulo p.

  Algoritmus: SFF (Négyzetmentes faktorizáció)
  Input: Egy Fq[x] beli főpolinom.
  Output: f négyzetmentes faktorizációja.
  i←1; R ← 1; gf′;
  if g ≠ 0 then {
     cgcd(f, g);
     wf/c;
     while w ≠ 1 do {
           ygcd(w, c); zw/y;
           RR·zi; i ← i+1; 
           wy; cc/y }
     if c ≠ 1 then {
           cc1/p;
           Output(R·SFF(c)p) }
     else  Output(R)
  else {
           ff1/p;
           Output(SFF(f)p) }
  end.

Example of a square-free factorization

szerkesztés

Let

 

to be factored over the field with three elements.

The algorithm computes first

 

Since the derivative is non-zero we have w = f/c = x2 + 2 and we enter the while loop. After one loop we have y = x + 2, z = x + 1 and R = x + 1 with updates i = 2, w = x + 2 and c = x8 + x7 + x6 + x2+x+1. The second time through the loop gives y = x + 2, z = 1, R = x + 1, with updates i = 3, w = x + 2 and c = x7 + 2x6 + x + 2. The third time through the loop also does not change R. For the fourth time through the loop we get y = 1, z = x + 2, R = (x + 1)(x + 2)4, with updates i = 5, w = 1 and c = x6 + 1. Since w = 1, we exit the while loop. Since c ≠ 1, it must be a perfect cube. The cube root of c, obtained by replacing x3 by x is x2 + 1, and calling the square-free procedure recursively determines that it is square-free. Therefore, cubing it and combining it with the value of R to that point gives the square-free decomposition

 

Distinct-degree factorization

szerkesztés

This algorithm splits a square-free polynomial into a product of polynomials whose irreducible factors all have the same degree. Let fFq[x] of degree n be the polynomial to be factored.

   Algorithm Distinct-degree factorization(DDF)
   Input: A monic square-free polynomial  fFq[x]
   Output: The set of all pairs (g, d), such that 
             f has an irreducible factor of degree d and
             g is the product of all monic irreducible factors of f of degree d.
   Begin
        
       while   do 
            
           if g ≠ 1, then 
              ;
             f* := f*/g;
           end if
           i := i+1;
       end while;
       if f* ≠ 1, then  ;
       if S = ∅
           then return {(f, 1)}
           else return S
    End

The correctness of the algorithm is based on the following:

Lemma. For i ≥ 1 the polynomial

 

is the product of all monic irreducible polynomials in Fq[x] whose degree divides i.

At first glance, this is not efficient since it involves computing the GCD of polynomials of a degree which is exponential in the degree of the input polynomial. However

 

may be replaced by

 

Therefore we have to compute:

 

there are two methods:

Method I. Start from the value of

 

computed at the preceding step and to compute its q-th power modulo the new f*, using exponentiation by squaring method. This needs

 

arithmetic operations in Fq at each step, and thus

 

arithmetic operations for the whole algorithm.

Method II. Using the fact that the q-th power is a linear map over Fq we may compute its matrix with

 

operations. Then at each iteration of the loop, compute the product of a matrix by a vector (with O(deg(f)2) operations). This induces a total number of operations in Fq which is

 

Thus this second method is more efficient and is usually preferred. Moreover, the matrix that is computed in this method is used, by most algorithms, for equal-degree factorization (see below); thus using it for the distinct-degree factorization saves further computing time.

Equal-degree factorization

szerkesztés

In this section, we consider the factorization of a monic squarefree univariate polynomial f, of degree n, over a finite field Fq, which has r ≥ 2 pairwise distinct irreducible factors   each of degree d.

We first describe an algorithm by Cantor and Zassenhaus (1981) and then a variant that has a slightly better complexity. Both are probabilistic algorithms whose running time depends on random choices (Las Vegas algorithms), and have a good average running time. In next section we describe an algorithm by Shoup (1990), which is also an equal-degree factorization algorithm, but is deterministic. All these algorithms require an odd order q for the field of coefficients. For more factorization algorithms see e.g. Knuth's book The Art of Computer Programming volume 2.

    Algorithm Cantor–Zassenhaus algorithm.
    Input: A finite field Fq of odd order q.
           A monic square free polynomial f in Fq[x] of degree n = rd, 
                which has r ≥ 2 irreducible factors each of degree d
    Output: The set of monic irreducible factors of f.
    Factors:={f};
    while Size(Factors) < r do,
       Choose h in Fq[x] with deg(h) < n at random;
        
       for each u in Factors with deg(u) > d do
           if gcd(g, u) ≠ 1 and gcd(g, u) ≠ u, then
             Factors:= Factors ;
           endif;
    endwhile
    return Factors.

The correctness of this algorithm relies on the fact that the ring Fq[x]/f is a direct product of the fields Fq[x]/fi where fi runs on the irreducible factors of f. As all these fields have qd elements, the component of g in any of these fields is zero with probability

 

This implies that the polynomial gcd(g, u) is the product of the factors of g for which the component of g is zero.

It has been shown that the average number of iterations of the while loop of the algorithm is less than  , giving an average number of arithmetic operations inFq which is  .[1]

In the typical case where dlog(q) > n, this complexity may be reduced to

 

by choosing h in the kernel of the linear map

 

and replacing the instruction

 

by

 

The proof of validity is the same as above, replacing the direct product of the fields Fq[x]/fi by the direct product of their subfields with q elements. The complexity is decomposed in   for the algorithm itself,   for the computation of the matrix of the linear map (which may be already computed in the square-free factorization) and O(n3) for computing its kernel. It may be noted that this algorithm works also if the factors have not the same degree (in this case the number r of factors, needed for stopping the while loop, is found as the dimension of the kernel). Nevertheless, the complexity is slightly better if square-free factorization is done before using this algorithm (as n may decrease with square-free factorization, this reduces the complexity of the critical steps).

Victor Shoup's algorithm

szerkesztés

Like the algorithms of the preceding section, Victor Shoup's algorithm is an equal-degree factorization algorithm.[2] Unlike them, it is a deterministic algorithm. However, it is less efficient, in practice, that the algorithms of preceding section. For Shoup's algorithm, the input is restricted to polynomials over prime fields Fq.

Let g = g1 ... gk be the desired factorization, where the gi are distinct monic irreducible polynomials of degree d. Let n = deg(g) = kd. We consider the ring R = Fq[x]/g and denote also by x the image of x in R. The ring R is the direct product of the fields Ri = Fq[x]/gi, and we denote by pi the natural homomorphism from the R onto Ri. The Galois group of Ri over Fq is cyclic of order d, generated by the field automorphism uup. It follows that the roots of gi in Ri are

 

If q > n, the Newton's identities allow to compute the si with

Like in the preceding algorithm, this algorithm uses the same subalgebra B of R as the Berlekamp's algorithm, sometimes called the "Berlekamp subagebra" and defined as

 

A subset S of B is said a separating set if, for every 1 ≤ i < j ≤ k there exists s ∈ S such that  . In the preceding algorithm, a separating set is constructed by choosing at random the elements of S. In Shoup's algorithm, the separating set is constructed in the following way. Let s in R[Y] be such that

 

Then   is a separating set because   for i =1, ..., k (the two monic polynomials have the same roots). As the gi are pairwise distinct, for every pair of distinct indexes (i, j), at least one of the coefficients sh will satisfy  

Having a separating set, Shoup's algorithm proceeds as the last algorithm of the preceding section, simply by replacing the instruction "choose at random h in the kernel of the linear map  " by "choose h + i with h in S and i in {1, ..., k−1}".

Rabin's test of irreducibility

szerkesztés

Like distinct-degree factorization algorithm, Rabin's algorithm[3] is based on the Lemma stated above. Distinct-degree factorization algorithm tests every d not greater than half the degree of the input polynomial. Rabin's algorithm takes advantage that the factors are not needed for considering fewer d. Otherwise, it is similar to distinct-degree factorization algorithm. It is based on the following fact.

Let p1, ..., pk, be all the prime divisors of n, and denote  , for 1 ≤ ik polynomial f in Fq[x] of degree n is irreducible in Fq[x] if and only if  , for 1 ≤ i ≤ k, and f divides  . In fact, if f has a factor of degree not dividing n, then f does not divide  ; if f has a factor of degree dividing n, then this factor divides at least one of the  

 Algorithm Rabin Irreducibility Test
 Input: A monic polynomial f in Fq[x] of degree n, 
        p1, ..., pk all distinct prime divisors of n.
 Output: Either "f is irreducible" or "f is reducible".
 Begin
     for j = 1 to k do 
         ;
     for i = 1 to k do 
         ;
        g := gcd(f, h);
        if g ≠ 1, then return 'f is reducible' and STOP;
     end for;
      ;
     if g = 0, then return "f is irreducible", 
         else return "f is reducible"
 end.

The basic idea of this algorithm is to compute   starting from the smallest   by repeated squaring or using the Frobenius automorphism, and then to take the correspondent gcd. Using the elementary polynomial arithmetic, the computation of the matrix of the Frobenius automorphism needs   operations in Fq, the computation of

 

needs O(n3) further operations, and the algorithm itself needs O(kn2) operations, giving a total of   operations in Fq. Using fast arithmetic (complexity   for multiplication and division, and   for GCD computation), the computation of the   by repeated squaring is  , and the algorithm itself is  , giving a total of   operations in Fq.

Lásd még

szerkesztés
  • KEMPFERT,H (1969) On the Factorization of Polynomials Department 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. (2001) Factoring Polynomials Over Finite Fields: A Survey . 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
  • Shoup, Victor (1989) New Algorithms for Finding Irreducible Polynomials over Finite Fields Computer Science Department University of Wisconsin–Madison
  • Geddes, K.O. (1990) Algorithms for Computer Algebra

Külső linkek

szerkesztés
  1. Flajolet, Philippe & Steayaert, Jean-Marc (1982), A branching process arising in dynamic hashing, trie searching and polynomial factorization, vol. 140, Lecture Notes in Comput. Sci., Springer, pp. 239–251
  2. Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990
  3. (1980) „Probabilistic algorithms in finite fields”. SIAM Journal on Computing 9 (2), 273–280. o. DOI:10.1137/0209024.