Re: Linear factors of very large polynomials

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

On Fri, Jan 29, 2021 at 12:20:44AM +0000, Neill Clift wrote:
> Hi,
> This is more of a question about the limits of computations pari/gp
> could do. This is not very important but it might be of interest to
> some people.
> So a few decades ago I realized eventually the password hashing
> algorithm in the OpenVMS operating system would be invertible. It was
> just a matter of machines getting enough memory and being able to do
> some large GCD's.
> In 2017 I asked a few questions here and got pari to actual find the
> linear factors of a large polynomial mod 2^64-59. The polynomial
> looked like this:
> 
> f(x) = x^16777213 - 24 * x^16777153 - 120 * x^3 - 198 * x^2 - 264 * x + 17748126081817865973
> 
> The constant term is different for each password that is to be found.
> I used FpX_roots(f,2^64-59) to find the factors. I think it took about
> 12 hours to do.

For what is worth, I tried with the latest PARI/GP version and it took
1h, 30min and 8GB of stack.

Time X^p-X: 3199085ms
Time gcd:   2205266ms

Cheers,
Bill