|Neill Clift on Sat, 31 Dec 2016 17:37:26 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Getting a very large polynomial into pari/gp|
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.