Re: Getting a very large polynomial into pari/gp

[Neill Clift <neillclift@live.com>]

On 12/31/2016 7:44 AM, Bill Allombert wrote:
> Are your polynomials univariate ?
> We have dedicated functions for handling univariate polynomials over
> finite fields.
Hi,
Yes the polynomials are univariate. Some 15 years ago I wrote some code 
to try and find the linear roots of this polynomial:

f(x) = x^16777213 - 24 * x^16777153 - 120 * x^3 - 198 * x^2 - 264 * x + c

For various constants c over the field F_p with p = 2^64-59

The code calculates g(x) = x^p-x mod f(x) by repeated squaring using FFT 
and 5 primes. The code was way to slow back then but now my home machine 
can do that calculation is a short time.
I am using the classical Euclidean gcd of g(x) and f(x) and that looks 
like it will take quite a few days to complete. I have had Pari/gp 
working on it over night but it has not finished yet. I did this:

(18:18) gp > a = Mod(Pol(read("a.gp")),2^64-59)
%1 = Mod(1, 18446744073709551557)*x^16777213 + Mod(18446744073709551533, 
18446744073709551557)*x^16777153 + Mod(18446744073709551437, 
18446744073709551557)*x^3 + Mod(18446744073709551359, 
18446744073709551557)*x^2 + Mod(18446744073709551293, 
18446744073709551557)*x + Mod(12702625443273995572, 18446744073709551557)
(18:21) gp > b = Mod(Pol(read("b.gp")),2^64-59)
%2 = Mod(2635936562008398736, 18446744073709551557)*x^16777212 + [+++]
(18:21) gp > gcd(a,b)

At some point I need to understand the Half GCD and maybe use that but I 
assumed Pari would use that.
I'll try a different method if there is one.
Thanks.
Neill.