Cómo puedo encontrar el menor entero $n$ tal que un polinomio divide $x^{n}-1$

Question

Tengo una pregunta sencilla...

Suponga que tengo un % polinomio arbitrario $f$$F_q[x]$.

¿Hay una forma práctica de encontrar el más pequeño número entero $n$ #% divide a que $f$% #%?

Se agradecería un pequeño ejemplo.

Gracias, por adelantado.

-Tengo mi propia respuesta por ahora para cualquier persona interesada, pero no tan prácticos como preferiría-

Answer 1

En el último que escribió este pequeño script en Magma; deje $\deg(f)=k$.

for i in [k..m] do
if Gcd(f,x^i-1) eq f then
print i;
end if;
end for;

Esto funciona bien para las pequeñas $k$: escriba en lugar de $'m'$ aquí, el siguiente; si $f=f_1.f_2...f_t$ por cada $f_j$ siendo irreductible factores de $f$,$m=q^{(\operatorname{lcm}({\deg f_j}))}-1$, que será precisamente el lugar donde $f$ se divide.

Vea este ejemplo;

> F<x>:=PolynomialRing(GF(3));
> f:= x^7-1-x^2-x^3;
> for i in [7..728] do
for> if Gcd(f1,x^i-1) eq f1 then
for|if> print i;
for|if> end if;
for> end for;`
104
208
312
416
520
624
728

Si usted también deseo la condición de que $\deg(f)$ divide $n$, entonces usted debe hacer;

    for i in [k..m] do
    if Gcd(f,x^i-1) eq f
    and Gcd(k,i) eq k then
    print i;
    end if;
    end for;

Para el ejemplo anterior, esto da el resultado $728$.

Pero para mayor $k$'s, el algoritmo necesita mucho tiempo..