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

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.

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

• you may also help with giving a SAGE or Magma script that does the job.. – S.B. Dec 3 '14 at 17:53
• Is $q$ a prime or a power of a prime? – lhf Dec 4 '14 at 12:44
• Any case Will be accepted, let it be prime for the beginning. – S.B. Dec 4 '14 at 12:46

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..