Re: Polrootsmod query

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

On Sat, Mar 12, 2011 at 07:54:24PM +0000, James Wanless wrote:
> 
> >>>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.
> 
> I _think_ I'm doing roughly the same as you, having looked at your
> 'FpX_roots_i'. Though you maybe have some extra code at the top half
> of your function, where you   /* take gcd(x^(p-1) - 1, f) by
> splitting (x^q-1) * (x^q+1) */ .
I was referring to the step 4 of algo 1.6.1.

> I only have the second part:   /* cf FpX_split_Berlekamp */
>  (onwards). Is this what you mean, and if so, might this matter?

This is a minor optimisation, this should make no difference.

> A degree 6/ prime size=490 (denary) digits is currently taking me ...
> 
> ... in the order of a day or two [though it's quite a lot faster for
> significantly smaller degrees/primes ie, not noticeably slowing down
> a primetest taking a few minutes overall, w/  smaller parameters,
> say degree 3/ prime size (100 denary) digits]
> Would you say this behaviour is possibly not totally unexpected, in
> general?

This is not possible unless there is some major problem with the modular 
polynomial arithmetic, like if sometimes some modular reductions (either
mod p or P) were missed.

Since you are using GMP, operations on degree 6 polynomials are fast.

Try to time which computations are slow and especially those that get very
slow when p is increased.

Cheers,
Bill.