|Bill Allombert on Sat, 12 Mar 2011 18:23:12 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Polrootsmod query|
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 the > results these give? [math question as opposed to coding question]. > If so, would this be of a similar (or even better?) efficiency > algorithm-wise, even though going via this route, ie via > _factorization_, rather than just root-finding directly, a more > complex algorithm involving matrices is needed? You could do that, but it would be slower for all the factorization algorithms I know. > >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. > >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 of > optimization going on in PARI that could be having a large positive > effect in this respect? Yes, at least you need subquadratic polynomial multiplication and euclidean remainder. What kind of degree/prime size are you interested in ? I have made some timings for polrootsmod(polcyclo(127),2^127-1): With GP 2.3.5 : 1,476 ms With GP 2.4.3+GMP5: 948 ms and polrootsmod(polcyclo(3541),16777259) With GP 2.3.5 : 2,220 ms With GP 2.4.3+GMP5: 1,268 ms Cheers, Bill.