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