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-

  • $\begingroup$ you may also help with giving a SAGE or Magma script that does the job.. $\endgroup$ – S.B. Dec 3 '14 at 17:53
  • $\begingroup$ Is $q$ a prime or a power of a prime? $\endgroup$ – lhf Dec 4 '14 at 12:44
  • $\begingroup$ Any case Will be accepted, let it be prime for the beginning. $\endgroup$ – 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;`

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.