Monday, 6 August 2012


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:
if bits < 5 and n > 128, then use B,
else if bits >= 5 and 2 * bits + n > 74, then use KS
else use CZ

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

No comments:

Post a Comment