Práctica 4: Polinomios

CoefficientList[polinomio,variable]

CoefficientList nos proporciona la lista de coeficientes del polinomio indicado.

CoefficientList[x^3 - 3  x + 5, x]

PolynomialMod[polinomio,p]

Reduce el polinomio módulo p.

PolynomialMod[x^3 - 3  x + 15, 7]

PolynomialQuotient[polinomio1,polinomio2,variable]

Proporciona el cociente de la división en Q[x] "polinomio1 entre polinomio2" respecto de la variable indicada.

a = x^4 - 2  x^3 + 2; b = 2  x^2 - 1;

q = PolynomialQuotient[a, b, x]

PolynomialRemainder[polinomio1,polinomio2,variable]

Proporciona el resto de la división en Q[x] "polinomio1 entre polinomio2" respecto de la variable indicada.

r = PolynomialRemainder[a, b, x]

a == Expand[b*q + r]

PolynomialGCD[polinomio1,polinomio2,...]

Proporciona el máximo común divisor de los polinomios indicados.

PolynomialGCD[x^2 - 4, x - 2]

PolynomialGCD[x^2 - 4, x - 2, x + 2]

PolynomialLCM[polinomio1,polinomio2,...]

Proporciona el mínimo común múltiplo de los polinomios indicados.

PolynomialLCM[x^2 - 4, x - 2]

PolynomialLCM[x^2 - 4, x - 2, x + 1]

Factor[polinomio]

Factoriza sobre Z[x] el polinomio indicado.

Factor[x^4 - 16]

Factor[4  x^2 - 9]

Factor[x^2 + 4]

Factor[polinomio,Modulus->p]

Factoriza el polinomio módulo el primo p (factoriza en (Subscript[Z, p])).

Factor[x^4 - 16, Modulus -> 7]

Factor[4  x^2 - 9, Modulus -> 7]

Factor[x^2 + 4, Modulus -> 7]

FactorList[polinomio]

Proporciona la factorización del polinomio.

FactorList[x^5 + x^4 + 2  x^3 + 2  x^2 - 3  x - 3]

FactorList[polinomio,Modulus->p]

Proporciona la factorización del polinomio módulo el primo p (factoriza en (Subscript[Z, p]) pero devuelve la factorización de forma distinta a Factor).

FactorList[x^4 - 16, Modulus -> 7]

FactorList[x^5 + x^4 + 2  x^3 + 2  x^2 - 3  x - 3, 
      Modulus -> 5]

La siguiente función proporciona el máximo común divisor de dos polinomios, así como los polinomios que nos permiten expresar dicho máximo común divisor como combinación lineal de los dos polinomios de entrada.

polynomialgcdext[X_,Y_]:=Module[{m,n,q,r,a,b,c,d,a0,b0,l,z,lista={}},
If[Y==0,Return[{X,{1,0}}]];
m=X;n=Y;q=PolynomialQuotient[m,n,x];r=PolynomialRemainder[m,n,x];
a=1; b=0;c=0;d=1;AppendTo[lista,{q,r,c,d}];
While[CoefficientList[r,x]!=CoefficientList[0,x],
	m=n;n=r;
	a0=a;b0=b;
	a=c;b=d;
	c=a0-q c;d=b0-q d;
	q=PolynomialQuotient[m,n,x];
	r=PolynomialRemainder[m,n,x];
	AppendTo[lista,{q,r,c,d}];
	];l=Length[CoefficientList[n,x]];z=CoefficientList[n,x][[l]];If[z!=1, n=Expand[(1/z)*n];c=Expand[(1/z)*c];d=Expand[(1/z)*d]];
	Return[{n,{c,d}}]]

polynomialgcdext[x^2 - 1, x^2 - 3  x + 2]

-1 + x == 
      Expand[1/3*(x^2 - 1) - 1/3*(x^2 - 3  x + 2)]

PolynomialGCD[x^2 - 1, x^2 - 3  x + 2]

polynomialgcdext[x^2 - 1, x^2 - 2]

1 == Expand[x^2 - 1 - (x^2 - 2)]

PolynomialGCD[x^2 - 1, x^2 - 2]

polynomialgcdext[x^3 - 3  x + 2, x^3 - 2  x^2 - x + 2]

-1 + x == 
      Expand[(x^3 - 3  x + 2)*(x/4 - 1/4) + (x^3 - 2  x^2 - x + 
                2)*(-x/4 - 1/4)]

PolynomialGCD[x^3 - 3  x + 2, x^3 - 2  x^2 - x + 2]

---------------------------------------------------------------------------------------------

La siguiente función calcula el polinomio interpolador de Newton en un cuerpo Z/pZ.

interpolacionnewton[lista_, 
        p_] := 
Module[{l, a, f, i, k, u, M, y, c, w, 
          s}, 
l = Length[lista]; 
a = 
          Table[lista[[i, 1]], {i, 1, l}]; 
f = 
          Table[lista[[i, 2]], {i, 1, l}]; 
M = 1; 
        u = f[[1]]; 
For[k = 2, 
          k <= l, k++, 
M = (x - a[[k - 1]])*
              M; 
y = 
            Table[M, {x, a[[k]], a[[k]]}]; 
c = 
            PowerMod[y[[1]], -1, p]; 
w = 
            Table[u, {x, a[[k]], a[[k]]}]; 
s = 
            Mod[(f[[k]] - w[[1]])*c, p]; 
u = 
            u + s*M]; 
        u = PolynomialMod[u, p]; 
Return[u]]

De este modo si queremos calcular un polinomio u(x) en (Z/7Z)[x] tal que u(2)=5, u(3)=4 y u(5)=1, daremos dos entradas: la primera, una lista de pares conteniendo los valores que queremos sustituir en la variable x de u(x) y su correspondiente imagen, y la segunda, el valor del primo p.

interpolacionnewton[{{2, 5}, {3, 4}, {5, 1}}, 7]

Efectivamente, si sustituimos y operamos obtenemos:

Mod[6 + 2 + 2^2, 7] == 5

Mod[6 + 3 + 3^2, 7] == 4

Mod[6 + 5 + 5^2, 7] == 1

----------------------------------------------------------------------------------------------------

A continuación vamos a ver una aplicación práctica de la reducibilidad de polinomios. Para ello definamos brevemente en qué consiste un registro de desplazamiento.
Un registro de desplazamiento es un sistema de celdas conectadas entre sí, con una conexión lineal entre algunas de las celdas y la entrada. Se dice entonces que la función de realimentación es no singular. El sistema debe de partir de un valor determinado denominado semilla y el modo de funcionamiento es el siguiente: el contenido de cada celda se desplaza un lugar a cada impulso del reloj, siendo el contenido del registro el valor que tiene entre dos impulsos consecutivos y la primera celda es realimentada con el valor de una operación que involucra a una o varias de los contenidos de las celdas del sistema. En el caso de los registros de desplazamiento realimentados linealmente, esta operación la hace una puerta XOR que combina los contenidos de las celdas conectadas a la misma.
Así el nuevo valor de S1 viene dado por:
	S1'=C1 S1 + C2 S2 + ....+ Cn Sn
donde + representaría la operación OR exclusivo, Si es el valor de la celda i-ésima (0 o 1) y Ci es un coeficiente que vale 0 o 1 en función de que la celda i-ésima esté o no conectada con la puerta XOR.
Si el registro tiene n etapas es claro entonces que el periodo máximo será de 2 elevado a n.
Todo sistema de este tipo lleva asociado un polinomio de la forma:
	p(x)=Cn x^n +.....+C2 x^2 + C1 x +1
con lo que las propiedades de este tipo de sistemas pueden estudiarse a través de dicho polinomio.

Pues bien, una aplicación de estos registros de desplazamiento es la generación de listas de números pseudoaleatorios.  Si cada estado del sistema es considerado como un número en base 2, la realimentación del registro nos va a producir listas de números pseudoaleatorios, la lista de los distintos estados del registro.  Una propiedad bastante importante es que la longitud de dicha lista puede ser o no fija, dependiendo de la reducibilidad o no del polinomio que caracteriza al registro. Si el polinomio es reducible (en Z2), entonces la longitud de la cadena depende de la semilla (ésta siempre ha de ser distinta de 000...000). Por el contrario, si el polinomio es irreducible, entonces todas las cadenas de números pseudoaletorios obtenidas a partir de distintas semillas tienen igual longitud

En primer lugar, evaluaremos la función cambioabase10 que nos permite cambiar a base 10 una lista x de dígitos expresados en base B.

cambioabase10[x_, B_] := 
        Module[{l, n, k}, l = 0; n = 1; 
          While[n <= Length[x], k = x[[n]]; l = B*l + k; n++]; 
          Return[l]];

La siguiente función recrea el funcionamiento de un registro de desplazamiento con polinomio característico introducido como primera variable y con semilla introducida como segunda variable.

aleatorios[polinomio_, lista_] := 
      Module[
{coeficientes, semilla, numeros, i, j, 
          aux}, 
coeficientes = 
          Drop[CoefficientList[polinomio, x], 
            1]; 
semilla = 
          lista; 
numeros = {cambioabase10[semilla, 
              2]}; 
nueva = 
          Table[semilla[[i - 1]], {i, 2, 
              Length[semilla]}]; 
aux = 
          0; 
For[j = 1, 
          j ≤ 
            Length[coeficientes], j++, 
aux = 
            aux + coeficientes[[j]]*
                semilla[[j]]]; 
PrependTo[nueva, 
          Mod[aux, 2]]; 
While[nueva ≠ semilla, 
          AppendTo[numeros, 
            cambioabase10[nueva, 2]]; 
aux = 
            0; 
For[j = 1, 
            j ≤ 
              Length[coeficientes], j++, 
aux = 
              aux + coeficientes[[j]]*
                  nueva[[j]]]; 
nueva = 
            Table[nueva[[i - 1]], {i, 2, 
                Length[nueva]}]; 
PrependTo[nueva, 
            Mod[aux, 2]]]; 
Return[numeros]]

p = x^4 + x^3 + x^2 + x + 1

Factor[p, Modulus -> 2]

Como vemos, p es irreducible. Comprobemos ahora todos las cadenas de números aleatorios que definen todas la posible semillas no nulas:

aleatorios[p, {0, 0, 0, 1}]

aleatorios[p, {0, 0, 1, 0}]

aleatorios[p, {0, 0, 1, 1}]

aleatorios[p, {0, 1, 0, 0}]

y así con todas se prueba rápidamente que tienen longitud 5.

p = x^4 + x^2 + 1

Factor[p, Modulus -> 2]

aleatorios[p, {0, 0, 0, 1}]

aleatorios[p, {0, 0, 1, 0}]

aleatorios[p, {0, 0, 1, 1}]

Sin embargo, si ahora probamos con la semilla {1,0,1,1} obtenemos

aleatorios[p, {1, 0, 1, 1}]

1- Calcule ahora las secuencias obtenidas con el polinomio x^4+x+1 y determine la relación entre las mismas.

2- Calcule un polinomio que nos permita generar secuencias de números aleatorios entre 1 y 63 y cuya longitud sea independiente de la semilla.

3- Calcule un polinomio que tenga la mismas características que el del ejercicio 1, pero que genere números entre 1 y 255.