James Wanless on Sat, 12 Mar 2011 22:01:12 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Polrootsmod query

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

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!