Re: Polrootsmod query

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

On 12 Mar 2011, at 20:44, Bill Allombert wrote:

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

Oh I see what you mean - no, I _am_ successfully skipping recursion on  
step 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.

Thanks again for this useful info

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

Aha, that _might_ be it. I haven't yet looked in detail, but although  
I had already checked I wasn't missing any modular reductions mod p,  
it had not occurred to me that reductions mod P (ie mod primitive  
polynomial?) could also be vital...

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

Thanks very much for all your help - you've given me both some good  
things to rule out, and some good new things to try!

> Cheers,
> Bill.

J