how can I find the smallest integer $n$ such that a polynomial divides $x^{n}-1$

Question

I have a simple question..

Assume that I have an arbitrary polynomial $f$ in $F_q[x]$.

Is there a practical way to find the smallest integer $n$ for which $f$ divides $x^n-1$ ?

A small example would be appreciated.

Thanks, in advance.

-I have my own answer for now for anyone interested, but not as practical as I would prefer-

Answer 1

At last I wrote this small script in Magma; let $\deg(f)=k$.

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

This works fine for small $k$: write in place of $'m'$ here, the following; if $f=f_1.f_2...f_t$ for each $f_j$ being irreducible factors of $f$, then $m=q^{(\operatorname{lcm}({\deg f_j}))}-1$, which will be exactly the place where $f$ splits.

See this example;

> 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

If you also desire the condition that $\deg(f)$ divides $n$, then you should do;

    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;

For the above example this gives the result $728$.

But for larger $k$'s, the algorithm needs much time..