Re: Polrootsmod query

[James Wanless <james@grok.ltd.uk>]

Hello Bill,
Thanks very much once again for your valued help. pls see below for  
response(s)...
J

On 12 Mar 2011, at 15:06, Bill Allombert wrote:

> On Sat, Mar 12, 2011 at 02:03:40PM +0000, James Wanless wrote:
> > Just realized I (probably?) sent this to the wrong list - I'll try
> > and get it right in future!
> >
> > > Why is PARI's implementation of polrootsmod so fast??? :)))
> > > I've implemented my own version using GMP and Algorithm 1.6.1 of
> > > Cohen ACCANT, but PARI's seems order(s) of magnitude faster.
> > > What algorithm does polrootsmod use, pls? Maybe Cantor-Zassenhaus
> > > split etc., ie Cohen Algorithms 3.4.x, using matrices?? I've
> > > looked at PARI's code and haven't (yet?) understood it, despite
> > > noticing a few references to 'Berlekamp'...
>
> Hello James,
>
> THe relevant C function is FpX_roots_i.

I am not totally clear (?)  - would it be feasible to work from  
'factormod' or 'factorcantor' and easily generate the roots from the  
results these give? [math question as opposed to coding question]. If  
so, would this be of a similar (or even better?) efficiency algorithm- 
wise, even though going via this route, ie via _factorization_, rather  
than just root-finding directly, a more complex algorithm involving  
matrices is needed?

> PARI use Cantor-Zassenhauss and follow essentially Algorithm 1.6.1.

Interesting... I wonder why your version is so much quicker than mine,  
then.

> Most of the time is spend in the computation of (X mod (p,P))^p
> (see remark (2) page 38). For that you need one of the algorithms
> of section 1.2 (binary powering).

Yes I believe I am already doing this correctly (I _was_ aware of  
remark 2, and have carefully checked I am not falling foul of that)

> You also need to implement fast polynomial arithmetic over Fp[X].

Maybe that's it... would you say, in general, that there's a lot of  
optimization going on in PARI that could be having a large positive  
effect in this respect?

> Note that PARI 2.4.3 is faster than PARI 2.3.5.

Which might seem to suggest 'yes' to my question immediately above.

> Cheers,
> Bill.