flint-devel

[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

Re: [flint-devel] polynomial modulo arithmetic

[William H. <ha...@ya...>]

--- Richard Howell-Peak <ric...@gm...> wrote:

> 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?

Yes, one can use a precomputed inverse in the same
way. I'm not sure how much more efficient that is than
what we do currently though. I use a pretty fast
algorithm for zmod_poly_divrem

> 
> 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. 

Yes, it is definitely worth implementing. The one
slight thing to watch out for is that it is possible
that by random chance the same irreducible polynomial
gets generated twice. Then you might think you have k
distinct polynomials which you have taken powers of,
when in reality you only have k-1. This may cause the
test to fail when it shouldn't, if not implemented
carefully.

> 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.

I've been factoring polynomials of the form x^{2n+1) -
1 and these seem to have quite a few factors. It's
true that a random polynomial over Z is probably
irreducible, but it isn't so over finite fields, it
seems.

By the way, the nullity of the Berlekamp algebra
actually turns out to be the number of irreducible
factors of f. Thus you can actually use the first part
of Berlekamp as an irreducibility test!!

> 
> 
> 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?

Yes, definitely. I believe the square-free part will
actually take very little of the run time.

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

That's actually up to you. There are two ways we can
go. We can optimise Berlekamp, or we can work on von
zur Gathen - Shoup. 

By the way, I found a way of taking more than a factor
of 2 off the time to do Gaussian reduction when you
have an extremely small prime modulus (like 5). 

Of course to really get the low, low times, one needs
to use asymptotically fast inversion (an algorithm due
to Strassen, which relies on an algorithm for matrix
multiplication, also due to Strassen) and use a packed
representation of the matrix (i.e. only 3 bits for
each entry in Z/5Z instead of a whole word). 

But those optmisations are not that interesting from
our perspective, since we care mainly about word sized
primes for now and optimising matrix operations takes
us well away from polynomial factorisation.

Bill.


      

Re: [flint-devel] polynomial modulo arithmetic

[William H. <ha...@ya...>]

By the way, a divrem should be faster than a mulmod by
1 if you want to reduce a polynomial mod f, since the
latter uses the former!

Bill.

--- Richard Howell-Peak <ric...@gm...> wrote:

> 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
> >
-------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your
> Move Developer's challenge
> Build the coolest Linux based applications with
> Moblin SDK & win great prizes
> Grand prize is a trip for two to an Open Source
> event anywhere in the world
>
http://moblin-contest.org/redirect.php?banner_id=100&url=/>
_______________________________________________
> flint-devel mailing list
> fli...@li...
>
https://lists.sourceforge.net/lists/listinfo/flint-devel
>