Factorización de polinomis sobre cossos finitos

En matemàtiques i càlcul simbòlic la factorización d'un polinomi consistix en descompondre-ho en un producte de factors irreducibles. Esta descomposició és teòricament possible i és única para polinomis en coeficients en qualsevol cos, pero es necessiten restriccions prou fortes en el cos dels coeficients per a permetre el càlcul de la factorización per mig d'un algoritme. En la pràctica, els algoritmes s'han dissenyat solament per a polinomis en coeficients en un cos finito, en els número racional o en una extensió de cossos d'un d'ells.

Tots els algoritmes d'factorización, inclós el cas dels polinomis en múltiples variables sobre els número racional, reduïxen el problema a este cas; vore factorización de polinomis. També s'utilisa per a diverses aplicacions de cossos finitos, com la teoria de còdics (còdics de verificació de redundància cíclica i el còdic BCH), criptografia (criptografia asimètrica per mig de curves elíptiques) i teoria de números computacional.

Com la reducció de la factorización de polinomis a la de polinomis d'una variable no té especificidad en el cas de coeficients en un cos finito, en este artícul solament es consideren polinomis en una variable.

Antecedents

Cos finito

Artícul principal → Cos finito.

La teoria de cossos finitos, els orígens dels quals es remonten als treballs de Carl Friedrich Gauss i Évariste Galois, ha jugat un important paper en vàries branques de les matemàtiques. Per la aplicabilidad del concepte en atres temes de matemàtiques i ciències com l'informàtica, hi ha hagut un resorgiment de l'interés en els cossos finitos, lo que es deu en part a importants aplicacions en teoria de còdics i criptografia. Les aplicacions de cossos finitos introduïxen alguns d'estos desenrolls en criptografia, càlcul simbòlic i teoria de còdics.

Un cos de Galois o cos finito és un cos en un orde finito (número d'elements). L'orde d'un cos finito és sempre un número primo o una potència d'un número primo. Per a cada potència primera q = p^r, existix exactament un cos finito en q elements, llevat isomorfisme. Este cos s'indica com GF(q) o F _q. Si p és primer, GF(p) és la característica d'orde p; és el cos de les classes de residus respecte al mòdul p, i els seus elements p es denoten 0, 1, ..., p-1. Aixina, a = b en GF(p) significa lo mateix que a ≡ b (mod p).

Polinomis irreducibles

Siga F un cos finito. Sobre els cossos generals, es diu que un polinomi no constant f en F[x] és irreducible sobre F si no és el producte de dos polinomis de grau positiu. Un polinomi de grau positiu que no és irreducible sobre F es diu reducible sobre F.

Els polinomis irreducibles permeten construir els cossos finitos d'orde no primer. De fet, per a una potència primària q, siga F_q el cos finito en q elements, únics salve per isomorfismes. Un polinomi f de grau n major que un, que és irreducible sobre F_q, definix una extensió de cos de grau n que és isomorfo al cos en qⁿ elements, que són els polinomis de grau inferior a n; la suma, resta i multiplicació per un element de F_q són els de els polinomis; el producte de dos elements és el restant de la divisió per f del seu producte com a polinomis; l'invers d'un element pot calcular-se per mig de l'algoritme MCD estés (vore aritmètica d'extensions algebraiques).

D'això es deduïx que, per a calcular en un cos finito d'orde no primer, és necessari generar un polinomi irreducible. Per a això, el método comú és prendre un polinomi a l'encert i provar el seu irreducibilidad. En benefici de l'eficiència de la multiplicació en el cos, és habitual buscar polinomis de la forma xⁿ + ax + b.

Els polinomis irreducibles sobre cossos finitos també són útils per als generadors de números pseudoaleatorios que utilisen registres de desplaçament de retroalimentación i logaritmos discrets sobre F_2ⁿ.

El número de polinomis mónicos irreducibles de grau n sobre F_q és el número de collars aperiódicos, donat per la funció de conteo de collars de Moreau M_q(n). La funció de collar estretament relacionada N_q(n) conta els polinomis mónicos de grau n que són primaris (una potència d'un irreducible); o, alternativament, polinomis irreducibles de tots els graus d que dividixen a n.^[1]

Eixemple

El polinomi P = x⁴ + 1 és irreducible sobre Q pero no sobre cap cos finito.

En qualsevol extensió de cos de F₂, P = (x + 1)⁴.
En tots els demés cossos finitos, a lo manco un de −1, 2 i −2 és un quadrat, perque el producte de dos no quadrats és un quadrat, per lo que es té que

Si $- 1 = a^{2},$ llavors $P = (x^{2} + a) (x^{2} - a) .$
Si $2 = b^{2},$ llavors $P = (x^{2} + b x + 1) (x^{2} - b x + 1) .$
Si $- 2 = c^{2},$ llavors $P = (x^{2} + c x - 1) (x^{2} - c x - 1) .$

Complexitat

Els algoritmes d'factorización polinomial utilisen operacions polinomiales bàsiques com a productes, divisions, màxim comú divisor (mcd), potències d'un polinomi en un atre mòdul, etc. Una multiplicació de dos polinomis de grau n com a màxim es pot realisar en operacions O(n²) en F_q usant aritmètica clàssica, o en O en les operacions (nlog(n) log (log (n))) en F_q usant aritmètica ràpida. Es pot realisar una divisió euclídea (divisió en restant) en periodos de temps similars. La dificultat d'obtindre un màxim comú divisor polinòmic entre dos polinomis de grau com a màxim n es pot prendre com a operacions O(n²) en F_q usant métodos clàssics, o com O(nlog²(n) log(log(n))) operacions en F_q usant métodos ràpits. Per a dos polinomis h i g de grau com a màxim n, la exponenciación h^q mod g es pot fer en O(log(q)) productes polinòmics, usant el método d'exponenciación binaria, és dir O(n²log(q)) operacions en F_q usant métodos clàssics, o O(nlog(q) log(n) log(log (n))) operacions en F_q usant métodos ràpits.

En els algoritmes que seguixen, les complexitat s'expressen en térmens de número d'operacions aritmètiques en F_q, utilisant algoritmes clàssics per a l'aritmètica de polinomis.

Algoritmes d'factorización

Molts algoritmes per a factorizar polinomis sobre cossos finitos inclouen les següents tres etapes:

Factorización lliure de quadrats
Factorización en graus distints
Factorización d'igual grau

Una excepció important és l'algoritme de Berlekamp, que combina les etapes 2 i 3.

Algoritme de Berlekamp

Artícul principal → Algoritme de Berlekamp.

L'algoritme de Berlekamp és històricament important per ser el primer algoritme d'factorización, que funciona be en la pràctica. No obstant, conté un bucle en els elements del cos subjacent, lo que implica que és practicable solament en menuts cossos finitos. Per a un cos subjacent fix, el seu complexitat temporal és polinomial, pero, per a cossos subjacents generals, la complexitat és exponencial segons el tamany del cos.

Factorización lliure de quadrats

L'algoritme determina una factorización lliure de quadrats per a polinomis els coeficients dels quals provenen del cos finito F_q d'orde q = p^m en p primer. Este algoritme determina primer la derivada i després calcula el mcd del polinomi i la seua derivada. Si no és un, el mcd torna a dividir el polinomi original, sempre que la derivada no siga zero (un cas que existix per a polinomis no constants definits sobre cossos finitos).

Este algoritme utilisa el fet de que, si la derivada d'un polinomi és zero, llavors és un polinomi en x^p, que és, si els coeficients pertanyen a F_p, la p potencia del polinomi obtingut en substituir x per x^1/p. Si els coeficients no pertanyen a F_p, la raïl p-ésima d'un polinomi en derivada zero s'obté per mig de la mateixa substitució en x, completada aplicant l'invers del automorfisme de Frobenius als coeficients.

Este algoritme funciona també sobre un cos de característica zero, en l'única diferència de que mai entra en els blocs d'instruccions a on es calculen les p raïls. No obstant, en este cas, l'algoritme de Yun és molt més eficient perque calcula els màxims divisores comuns de polinomis de graus inferiors. Una conseqüència és que, al factorizar un polinomi sobre els sancers, no s'utilisa l'algoritme que seguix: primer es calcula la factorización lliure de quadrats sobre els sancers, i per a factorizar els polinomis resultants, s'elegix un p tal que permaneixen lliures de quadrats de mòdul p.

Algoritme: SFF (Factorización sense quadrats)
    Entrada: Un polinomi mónico f en F_q [x] a on q = p^m
    Eixida: Factorización lliure de quadrats de f
    R ← 1
   
    # Fer que w siga el producte (sense multiplicitat) de tots els factors de f que tenen
    # multiplicitat no divisible per p
    c ← mcd (f, f′)
    w ← f/c
   
    # Passe 1: Identificar tots els factors en w
    i ← 1
    mentresw ≠ 1 fer
        i ← mcd (w, c)
         fac  ← w/i
        R ← R · facⁱ
        w ← i; c ← c/i; i ← i + 1
    terminar mentres
    # c és ara el producte (en multiplicitat) dels factors restants de f
   
    # Passe 2: identificar tots els factors restants per mig de recursividad
    # Tinga's en conte que estos són els factors de f que tenen multiplicitat divisible per p
    si c ≠ 1 llavors
        c ← c^1/p
        R ← R · SFF (c)^p
    terminar si
   
    Eixida (R)

L'idea és identificar el producte de tots els factors irreducibles de f en la mateixa multiplicitat. Açò es fa en dos passos. El primer pas usa la derivada formal de f per a trobar tots els factors en multiplicitat no divisible per p. El segon pas identifica els factors restants. Com tots els factors restants tenen multiplicitat divisible per p, lo que significa que són potències de p, simplement es pot prendre la raïl quadrada de p i aplicar la recursividad.

Eixemple d'factorización lliure de quadrats

Siga

f = x^{11} + 2 x^{9} + 2 x^{8} + x^{6} + x^{5} + 2 x^{3} + 2 x^{2} + 1 \in 𝐅_{3} [x],

que es desija factorizar sobre el cos en tres elements.

L'algoritme calcula primer

c = \gcd (f, f^{'}) = x^{9} + 2 x^{6} + x^{3} + 2.

Ya que la derivada no és zero, es té que $w = f / c = x 2 + 2$ i s'entra en el cicle mentres. Despuix d'un bucle es té que $i = x + 2$ , $z = x + 1$ i $R = x + 1$ en actualisacions $i = 2$ , $w = x + 2$ i $c = x 8 + x 7 + x 6 + x 2 + x +1$ . La segona volta a través del cicle resulta $i = x + 2$ , $z = 1$ , $R = x + 1$ , en actualisacions $i = 3$ , $w = x + 2$ i $c = x 7 + 2 x 6 + x + 2$ . La tercera volta a través del bucle tampoc canvia $R$ . Passant per quarta volta a través del bucle s'obté $i = 1$ , $z = x + 2$ , $R = (x + 1)(x + 2) 4$ , en actualisacions $i = 5$ , $w = 1$ i $c = x 6 + 1$ . Ya que w = 1, s'ix del bucle mentres. Ya que c ≠ 1, deu ser una gaveta perfecta, la raïl cúbica de c, obtinguda en reemplaçar x³ per x és x² + 1, i cridar al procediment sense quadrats determina de forma recursiva que el resultat està lliure de quadrats. Per lo tant, dividir-ho en una gaveta i combinar-ho en el valor de R fins a eixe punt dona la descomposició sense quadrats

f = (x + 1) (x^{2} + 1)^{3} (x + 2)^{4} .

Factorización de graus distints

Este algoritme dividix un polinomi lliure de quadrats en un producte de polinomis els factors dels quals irreducibles tenen tots el mateix grau. Siga f ∈ F_q[x] de grau n el polinomi a factorizar.

Algoritme Factorización de graus distints (DDF)
    Entrada: Un polinomi mónico lliure de quadrats  $f \in F q [x]$ 
    Eixida: El conjunt de tots els parells  $(g, d)$ , tals que
              $f$  té un factor irreducible de grau  $d$  i
              $g$  és el producte de tots els factors mónicos irreducibles de  $f$  de grau  $d$ .
    Escomençar
         $i : = 1; S : = \emptyset, f^{*} : = f;$ 
        mentres  $\deg f^{*} \geq 2 i$  fer
             $g = mcd (f^{*}, x^{q^{i}} - x)$ 
            si  $g \neq 1$ , llavors
                 $S : = S \cup {(g, i)}$ ;
                 $f^{*} : = f^{*} / g$ 
            terminar si
             $i := i + 1;$ 
        fi  mentres;
        si  $f^{*} \neq 1$ , llavors  $S : = S \cup {(f^{*}, \deg f^{*})}$ ;
        si  $S = \emptyset$ , llavors torna  $Plantilla:Mset$ ,
            si no torna  $S$ 
    Final

La correcció de l'algoritme es basa en lo següent:

A primera vista, este procediment no és eficient, ya que implica calcular el MCD de polinomis d'un grau que és exponencial en el grau del polinomi d'entrada. No obstant

g = mcd (f^{*}, x^{q^{i}} - x)

pot ser reemplaçat per

g = mcd (f^{*}, (x^{q^{i}} - x mod f^{*})) .

Per lo tant, es té que calcular:

x^{q^{i}} - x mod f^{*},

hi ha dos métodos:

Factorización d'igual grau

Algoritme de Cantor-Zassenhaus

Artícul principal → Algoritme de Cantor-Zassenhaus.

En esta secció, es considera la factorización d'un polinomi mónico d'una variant lliure de quadrats f, de grau n, sobre un cos finito F_q, que té r ≥ 2 factors irreducibles distints per parells $f_{1}, \dots, f_{r}$ cada u de grau d.

Primer es descriu un algoritme de Cantor i Zassenhaus (1981) i després una variant que té una complexitat llaugerament millor. Abdós són algoritmes provabilístics el temps dels quals d'eixecució depén d'eleccions aleatòries (algoritme de Las Vegas) i tenen un bon temps d'eixecució mig. En la següent secció es descriu un algoritme de Shoup (1990), que també és un algoritme d'factorización d'igual grau, pero és determinista. Tots estos algoritmes requerixen un orde impar q del cos de coeficients. Per a obtindre més algoritmes d'factorización, consulte's per eixemple el llibre de Knuth The Art of Computer Programming volum 2.

Algoritme Algoritme de Cantor-Zassenhaus.
    Entrada: Un cos finito F_q d'orde impar q.

Un polinomi mónico lliure de quadratsf en F_q [x] de grau n = rd,

                que té r ≥ 2 factors irreducibles cada u de grau d
    Eixida: El conjunt de factors mónicos irreducibles de f.

    Factors: = {f};
    mentres Tamany (factors) < r fer,
        Elegir h en F_q [x] en graus (h) < n aleatoriamente;
         $g : = h^{\frac{q^{d} - 1}{2}} - 1 (\mod f)$ 
        per a cada o en Factors en deg(o) > d fer
            si mcd (g, o) ≠ 1 i mcd(g, o) ≠ o, llavors
                Factors: = Factors $∖ {u} \cup {(\gcd (g, u), u / \gcd (g, u))}$ ;
            terminar si;
    mentrestant

    Tornar els factors

L'exactitut d'este algoritme es basa en el fet de que l'anell F_q[x]/f és un producte directe dels cossos F_q[x]/f_i a on f_i s'eixecuta en els factors irreductibles de f. Com tots estos cossos tenen q^d elements, el component de g en qualsevol d'estos cossos és zero en provabilitat

\frac{q^{d} - 1}{2 q^{d}} \sim \frac{1}{2} .

Açò implica que el polinomi mcd (g, o) és el producte dels factors de g per als quals el component de g és zero.

S'ha demostrat que el número mig de iteraciones del bucle mentres de l'algoritme és menor que $2.5 \log_{2} r$ , lo que dona un número mig d'operacions aritmètiques en F_q que és $O (d n^{2} \log (r) \log (q))$ .^[2]

En el cas típic quan d log (q) > n, esta complexitat pot reduir-se a

O (n^{2} (\log (r) \log (q) + n))

elegint h en el núcleu de l'aplicació llineal

v \to v^{q} - v (\mod f)

i reemplaçant l'instrucció

g : = h^{\frac{q^{d} - 1}{2}} - 1 (\mod f)

per

g : = h^{\frac{q - 1}{2}} - 1 (\mod f) .

La prova de validea és la mateixa que l'anterior, reemplaçant el producte directe dels cossos F_q[x]/f_i pel producte directe dels seus subcuerpos en q elements. La complexitat es descompon en $O (n^{2} \log (r) \log (q))$ per a l'algoritme en sí, $O (n^{2} (\log (q) + n))$ per al càlcul de la matriu de l'aplicació llineal (que pot estar ya calculat en la factorización lliure de quadrats) i O(n³) per a computar el seu núcleu. cal senyalar que este algoritme també funciona si els factors no tenen el mateix grau (en este cas, el número "r" de factors, necessari per a detindre el cicle mentres, es troba com la dimensió del núcleu). No obstant, la complexitat és llaugerament millor si es realisa la factorización sense quadrats abans d'usar este algoritme (ya que n pot disminuir en la factorización sense quadrats, açò reduïx la complexitat dels passos crítics).

Algoritme de Victor Shoup

Com els algoritmes de la secció anterior, l'algoritme de Victor Shoup és un algoritme d'factorización d'igual grau.^[3] A diferència d'ells, és un algoritme determinista. No obstant, és menys eficient, en la pràctica, que els algoritmes de la secció anterior. Per a l'algoritme de Shoup, l'entrada està restringida a polinomis sobre cossos primers F _p.

El pijor cas de complexitat temporal de l'algoritme de Shoup té un factor $\sqrt{p} .$ . Encara que exponencial, esta complexitat és molt millor que la dels algoritmes determinista anteriors (algoritme de Berlekamp) que tenen com a factor $p$ . No obstant, hi ha molt pocs polinomis per als quals el temps de càlcul és exponencial i la complexitat de temps promig de l'algoritme és polinomial en $d \log (p),$ a on $d$ és el grau del polinomi i $p$ és el número d'elements del cos subjacent.

Siga g = g₁ ... g_k la factorización desijada, a on g_i són polinomis mónicos irreducibles distints de grau d. Siga n = deg(g) = kd. Considere's l'anell R = F_q[x]/g i es denota també per x l'image de x en R. L'anell R és el producte directe dels cossos R_i = F_q[x]/g_i, i es denota per p_i el homomorfisme natural de R sobre R_i. El grup de Galois de R_i sobre F_q és cíclico d'orde d, generat pel automorfisme o → o^p. D'això es deduïx que les raïls de g_i en R_i són

p_{i} (x), p_{i} (x^{q}), p_{i} (x^{q^{2}}), p_{i} (x^{q^{d - 1}}) .

Com en l'algoritme anterior, este algoritme usa la mateixa subálgebra B sobre R que l'algoritme de Berlekamp, a voltes denominada subálgebra de Berlekamp i definida com

\begin{matrix} B & = {α \in R : p_{1} (α), \dots, p_{k} (α) \in 𝐅_{q}} \\ = {u \in R : u^{q} = u} \end{matrix}

Un subconjunt S de B es diu un conjunt en separació si, per cada 1 ≤ i < j ≤ k existix un s ∈ S tal que $p_{i} (s) \neq p_{j} (s)$ . En l'algoritme anterior, es construïx un conjunt en separació elegint a l'encert els elements de S. En l'algoritme de Shoup, el conjunt en separació es construïx de la següent manera. Siga s en R[I] tal que

\begin{matrix} s & = (Y - x) (Y - x^{q}) \dots (Y - x^{q^{d - 1}}) \\ = s_{0} + \dots + s_{d - 1} Y^{d - 1} + Y^{d} \end{matrix}

Llavors ${s_{0}, \dots, s_{d - 1}}$ és un conjunt en separació perque $p_{i} (s) = g_{i}$ per a i = 1, ..., k (els dos polinomis mónicos tenen les mateixes raïls). Com els g_i són distints per parells, per a cada parell d'índexs distints (i, j), a lo manco un dels coeficients s_h satisfarà $p_{i} (s_{h}) \neq p_{j} (s_{h}) .$

Tenint un conjunt en separació, l'algoritme de Shoup procedix com l'últim algoritme de la secció anterior, simplement reemplaçant l'instrucció "elegir a l'encert h en el núcleu de l'aplicació llineal $v \to v^{q} - v (\mod f)$ " per "elegir (h + i) en h en S i i en {1, ...,k - 1}".

Vore també

Referències

↑ Christophe Reutenauer, Mots circulaires et polynomes irreductibles, Ann. Sci. math Quebec, vol 12, no 2, pp. 275-285
↑ (1982).«Automata, Languages and Programming».Springer.140
239–251.doi:10.1007/BFb0012773.
↑ Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990

Bibliografia

KEMPFERT, H (1969) 'Factorización de polinomis' ' Departament de Matemàtiques, Universitat Estatal d'Ohio, Columbus, Ohio 43210
Shoup, Victor (1996) Suavitat i factorización de polinomis sobre cossos finitos Departament de Ciències de la Computació de l'Universitat de Toronto
Von Zur Gathen, J.; Panario, D. (2001). Factorización de polinomis sobre cossos finitos: una enquesta. Journal of Symbolic Computation, Volum 31, números 1 a 2, giner de 2001, 3 a 17.
Gao Shuhong, Panario Daniel, "Prova i construcció de polinomis irreducibles sobre cossos finitos", Departament de Ciències Matemàtiques, Universitat de Clemson, Carolina del Sur, 29634-1907, EE. UU. i el Departament de Ciències de la Computació de l'Universitat de Toronto, Canadà M5S-1A4
Shoup, Victor (1989) Nou Algoritmes per a trobar polinomis irreducibles en cossos finitos Departament de Ciències de la Computació Universitat de Wisconsin & ndash; Madison
Geddes, Keith O.; Czapor, Stephen R .; Labahn, George (1992). Algoritmes per a àlgebra informàtica. Boston, MA: Kluwer Academic Publishers. págs. xxii + 585. ISBN 0-7923-9259-0.

Referències

Este artícul conté una traducció derivada de «Factorización de polinomios sobre cuerpos finitos» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Christophe Reutenauer, Mots circulaires et polynomes irreductibles, Ann. Sci. math Quebec, vol 12, no 2, pp. 275-285

[2] (1982).«Automata, Languages and Programming».Springer.140
239–251.doi:10.1007/BFb0012773.

[3] Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990

[1]

[2]

[3]