Bill Allombert on Sat, 31 Dec 2016 18:05:05 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Getting a very large polynomial into pari/gp |
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.