[flint-devel] polynomial modulo arithmetic

[Richard Howell-P. <ric...@gm...>]

It would be good to have a simple function for reducing a polynomial mod f,
at the moment I have just been doing mulmod and multiplying by the constant
polynomial 1. I know for integers there is a more efficient way of doing
this than a divrem, is that the case for polynomials as well?

I have also devised a test for berlekamp's algorithm which I would like to
know if it is worth implementing. It involves generating random polynomials
of random length and testing them for irreducibility (using the irreducible
test I have re-written since losing it)  and keeping them if they are
irreducible. We then raise them to random powers and compute the product and
attempt to reclaim the factors. The alternative is to simply run berlekamp
on random polynomials and then test all the factors and see if they are
irreducible or not. This has the advantage of being quicker but I suspect
most polynomials will be irreducible and therefore unaffected by berlekamp.


Also should I implement a more generic function:

zmod_poly_factor(zmod_poly_factor_t factors, zmod_poly_t input)

which will automatically call square-free and then berlekamp accordingly?


Lastly is it worth beginning work on distinct degree, equal degree
factorisation algorithms or do you want to focus on optimising berlekamp?

-- 
Richard