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


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?