I wrote in my previous post that Cantor and Zassenhaus' algorithm of polynomial factorisation over finite fields can be divided into three stages:

According to Modern Computer Algebra, "the second stage consumes the bulk of the computing time". In 1998 Erich Kaltofen and Victor Shoup designed a new approach to distinct-degree factorisation which allows to decrease it's cost. This strategy is called "baby/giant step" and exploits the fact from number theory:

- squarefree factorisation
- distinct-degree factorisation
- equal-degree factorisation

(in the standard Cantor-Zassenhaus algorithm the squarefree factorisation step is merged with the algorithm itself)

*Lemma.*For nonnegative integers $i$ and $j$, the polynomial $x^{q^i} - x^{q^j} \in F_q [x]$ is divisible by precisely those irreducible polynomials in $F_q [x]$ whose degree divides $i−j$.

The proof is easy: if $i \geq j$ then $x^{q^i} - x^{q^j} = (x^{q^{i-j}} - x)^{q^j}$. From the

*Theorem*from the previous post we know that the factorisation of $x^{q^k} - x$ consists of all irreducible factors whose degree is a divisor of $k$.
Now it's possible to formulate the algorithm:

__Fast distinct-degree factorisation (DDF)__

__Input and output__
This algorithm takes as input a square-free polynomial $f \in F_q [x]$ of degree $n$.

The output is $f ^{[1]} , . . . , f^{[n]} \in F_q [x]$ such that for $1 \leq d \leq n$, $f ^{[d]}$ is the product of the monic irreducible factors of f of degree $d$. The algorithm is parameterized by a constant $\beta$, with $0 \leq \beta \leq 1$.

__Step 1 (compute baby steps)__
Let $l = \lceil n\beta \rceil$ . For $0\leq i\leq l$, compute $h_i = x^{q^i} \mod f$.

__Step 2 (compute giant steps)__
Let $m = \lceil \frac{n}{2l} \rceil$ . For $1\leq j\leq m$, compute $H_j = x^{q^{lj}} \mod f$.

**Step 3 (compute interval polynomials)**
For $1\leq j\leq m$, compute $I_j = \prod\limits_{0\leq i\leq l}(H_j - h_i) \mod f$ .

(by

*Lemma*the polynomial $I_j$ is divisible by those irreducible factors of $f$ whose degree divides an integer $k$ with $(j-1)l < k \leq jl$)

**Step 4 (compute coarse DDF)**
In this step, we compute polynomials $F_1, ... , F_m $ where $F_j = f^{[(j-1)l+1]} f^{[(j-1)l+2]} ... f^{[jl]}$. This is done as follows.

$s\leftarrow f;$

for $j \leftarrow 1$ to $m$ do

$\left\{F_j \leftarrow \gcd(s, I_j); s\leftarrow \frac{s}{F_j}\right\}$

$s\leftarrow f;$

for $j \leftarrow 1$ to $m$ do

$\left\{F_j \leftarrow \gcd(s, I_j); s\leftarrow \frac{s}{F_j}\right\}$

__Step 5 (compute fine DDF)__
In this step, we compute the output polynomials $f^{[1]}, ... , f ^{[n]}$.

First, initialize $f^{[1]}, ... , f^{[n]}$ to 1. Then do the following.

for $j \leftarrow1$ to $m$ do

{

$g\leftarrow F_j ;$

for $i\leftarrow l - 1$ down to 0 do

$\left\{ f^{[lj-i]} \leftarrow \gcd(g, H_j - h_i); g\leftarrow \frac{g}{f^{[lj-i]}} \right\}$

$\left\{ f^{[lj-i]} \leftarrow \gcd(g, H_j - h_i); g\leftarrow \frac{g}{f^{[lj-i]}} \right\}$

}

if $s \neq 1$ then $f^{[\deg(s)]}\leftarrow s$

**Some technical remarks**
1.

*Lemma.*For any positive integer $r$ if we are given $h = x^{q^r} \mod f \in F_q [x]$, then for any $g \in F_q [x]$, we can compute $g^{q^r} \mod f$ as $g(h) \mod f$.
Now to perform Step 2 we set $H_1 = h_l$ and then compute each $H_j$ as $H_{j−1} (H_1) \mod f$.

2. Computing $f(g) \mod h$ is a so-called "modular composition" problem. For solving this problem one can use e.g. Horner scheme or Brent and Kung's algorithm (this also requires fast matrix multiplication).

By now I implemented the simplest version of the fast CZ algorithm: it uses Horner scheme in Step 2.

The next step might be to implement matrix multiplication and Brent and Kung's algorithm.

## No comments:

## Post a Comment