Bill Allombert on Sat, 12 Mar 2011 21:51:42 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Polrootsmod query |
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.