Re: [Fastlibnt-devel] Additional polynomial functions

[David H. <dmh...@ma...>]

On Apr 24, 2007, at 10:36 PM, William Hart wrote:

> Another few important functions we have forgotten for
> polynomials:
>
> polynomial composition

This is easy to do badly, and tricky to do well. I expect it's much  
easier over a finite field than over Z.

You might want to add reversion (functional inverse) to this list. I  
recall it can be reduced to composition (and vice versa).

> polynomial factorization

This is what NTL is very proud of, as far as I can tell. I don't know  
much about factorisation algorithms, but I got the impression that to  
do factorisation in Z[x], you really want to start with factorisation  
over Z/p[x].

> polynomial roots (over the integers)

I have no idea about algorithms for this.

> polynomial evaluation (at an integer)

Trivial to evalute at a single point. Much harder if you start  
wanting to support fast multipoint evaluation and related things. NTL  
has an interface for such things, but he only implements the trivial  
algorithms so far.

> resultant of polynomials

I have no idea how to do this efficiently. I might check out NTL for  
some ideas.

> derivative of polynomials

'nuff said.

Many of the algorithms for polynomials over Z are most easily  
implemented on top of algorithms for polynomials over Z/p[x]. I'm  
wondering how far we will get before we need to implement a Zmod_poly  
layer.

David