Re: Polrootsmod query

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Sat, Mar 12, 2011 at 04:05:16PM +0000, James Wanless wrote:
> Hello Bill,
> >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?

You could do that, but it would be slower for all the factorization algorithms
I know.

> >PARI use Cantor-Zassenhauss and follow essentially Algorithm 1.6.1.
> 
> Interesting... I wonder why your version is so much quicker than
> mine, then.

Maybe you do not skip step 1 in the recursion.

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

Yes, at least you need subquadratic polynomial multiplication and 
euclidean remainder.

What kind of degree/prime size are you interested in ?

I have made some timings for polrootsmod(polcyclo(127),2^127-1):

With GP 2.3.5     : 1,476 ms
With GP 2.4.3+GMP5:   948 ms

and
polrootsmod(polcyclo(3541),16777259)

With GP 2.3.5     : 2,220 ms
With GP 2.4.3+GMP5: 1,268 ms

Cheers,
Bill.