Sometimes it is very helpful to have a function which makes an automatic choice between available factorisation algorithms depending on an input polynomial. For this purpose I wrote some profiling code in nmod_poly and fmpz_mod_poly_factor. The results are as follows (along Oy axis: $y, n=2^y$, where $n$ is a degree of input polynomial, along Ox: $x=bits(q)$ is number of bits in modulo, the letters denote the boarder where one algorithm becomes faster than another: B - Berlekamp, CZ - Cantor-Zassenhaus, KS - Kaltofen-Shoup).

I tried to make a simple formula which fits these data. Finally, I got:

nmod_poly:

if bits < 5 and n > 128, then use B,

else if bits >= 5 and 2 * bits + n > 74, then use KS

else use CZ

fmpz_mod_poly:

if 5 * bits + n > 75, then use KS, else use CZ

__nmod_poly__**:**__fmpz_mod_poly:__I tried to make a simple formula which fits these data. Finally, I got:

nmod_poly:

if bits < 5 and n > 128, then use B,

else if bits >= 5 and 2 * bits + n > 74, then use KS

else use CZ

fmpz_mod_poly:

if 5 * bits + n > 75, then use KS, else use CZ

## No comments:

## Post a Comment