Re: Getting a very large polynomial into pari/gp

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Dec 31, 2016 at 04:37:15PM +0000, Neill Clift wrote:
> 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.

The libpari library provides a set of functions to deal with polynomials
over F_p that implement the half-GCD algorithm but they are not directly
available in GP.

Try:
install("FpX_gcd","GGG")
p = 2^64-59;
a = Pol(read("a.gp"));
b = Pol(read("b.gp"));
FpX_gcd(a,b,p)

and actually since p is less than 2^64 there is another function that
use a more compact representation of polynomials (Vecsmall), but the
above function will do the conversions for you.
Read about FpX, FpX_gcd, Flx and Flx_gcd in the documentation.

If you use Windows make sure to use the installer and ot the stand-alone
binary. Unfortunately install() does not work with the stand-alone
binary.

For this kind of computation, you should consider using the PARI library
directly.

Cheers,
Bill.