*Fact.*A polynomial $f\in F_q[x]$ of degree $n\geq 1$ is irreducible if and only if

1) $x^{q^n}\equiv x \mod f$ and

2) $\gcd (x^{q^{n/t}}-x, f)=1$ for all prime divisors $t$ of $n$.

From this fact one can get the Rabin's irreducibility test:

__Irreducibility test (Rabin)____Input and Output__On input we have $f\in F_q[x]$ of degree $n$. On output test gives an answer "reducible" or "irreducible".

__Step 1.__Compute $a=x^{q^n} \mathrm{rem} f$. If $a\neq x$ return

**"reducible"**.

__Step 2.__Find prime divisors of $n$.

**Step 3.**For all prime divisors $t$ of $n$ compute $b=x^{q^{n/t}} \mathrm{rem} f$. If $\gcd(b-x, f)\neq 1$ return

**"reducible"**.

__Step 4.__Return

**"irreducible"**.

Another possibility is to use distinct-degree factorisation to test irreducibility.

**Irreducubility test (ddf)**__Step 1.__Check if $f$ is squarefree (by computing it's derivative). If not, return

**"reducible"**.

__Step 2.__Build ddf $f^{[1]},...,f^{[n]}$ for $f$.

__Step 3.__If $\deg f^{[n]}=n$ return

**"irreducible"**, else return

**"reducible"**.

Since fmpz_mod_poly doesn't have fast gcd computation and fast modular composition implemented, the ddf-based algorithm turns out to be faster for it.

## No comments:

## Post a Comment