James Wanless on Sat, 12 Mar 2011 20:56:43 +0100

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

 Re: Polrootsmod query

 On 12 Mar 2011, at 17:16, Bill Allombert wrote: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 theresults these give? [math question as opposed to coding question].If so, would this be of a similar (or even better?) efficiencyalgorithm-wise, even though going via this route, ie via_factorization_, rather than just root-finding directly, a morecomplex algorithm involving matrices is needed?You could do that, but it would be slower for all the factorization algorithmsI know.Thanks for that info (that reduces the options helpfully :)PARI use Cantor-Zassenhauss and follow essentially Algorithm 1.6.1.Interesting... I wonder why your version is so much quicker thanmine, 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 only have the second part:   /* cf FpX_split_Berlekamp */ (onwards). Is this what you mean, and if so, might this matter?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 ofoptimization going on in PARI that could be having a large positiveeffect in this respect?Yes, at least you need subquadratic polynomial multiplication and euclidean remainder.What kind of degree/prime size are you interested in ?A degree 6/ prime size=490 (denary) digits is currently taking me ...I have made some timings for polrootsmod(polcyclo(127),2^127-1):With GP 2.3.5     : 1,476 msWith GP 2.4.3+GMP5:   948 msandpolrootsmod(polcyclo(3541),16777259)With GP 2.3.5     : 2,220 msWith GP 2.4.3+GMP5: 1,268 ms... 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?Cheers,Bill.thanks,James